322:
211:
296:
Adam Tauman Kalai, Yishay
Mansour, and Elad Verbin, โOn agnostic boosting and parity learning,โ in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 629–638,
304:
Oded Regev, โOn lattices, learning with errors, random linear codes, and cryptography,โ in
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93,
115:
121:
293:
Avrim Blum, Adam Kalai, and Hal
Wasserman, โNoise-tolerant learning, the parity problem, and the statistical query model,โ J. ACM 50, no. 4 (2003): 506–519.
266:
363:
244:
Wasserman, Hal; Kalai, Adam; Blum, Avrim (2000-10-15). "Noise-Tolerant
Learning, the Parity Problem, and the Statistical Query Model".
47:
of bits at some fixed locations. The samples are generated using some distribution over the input. The problem is easy to solve using
51:
provided that a sufficient number of samples (from a distribution which is not too skewed) are provided to the algorithm.
387:
356:
215:
The noisy version of the parity learning problem is conjectured to be hard and is widely used in cryptography.
349:
382:
136:
206:{\displaystyle y={\begin{cases}f(x),&{\text{if }}b\\1-f(x),&{\text{otherwise}}\end{cases}}}
82:
59:
In
Learning Parity with Noise (LPN), the samples may contain some error. Instead of samples (
224:
48:
8:
337:
329:
306:
245:
274:
International
Conference on Current Trends in Theory and Practice of Computer Science
277:
20:
44:
298:
281:
333:
376:
54:
321:
250:
23:. An algorithm that solves this problem must find a function
199:
307:
http://portal.acm.org/citation.cfm?id=1060590.1060603
124:
85:
243:
205:
109:
374:
267:"Cryptography from learning parity with noise"
357:
299:http://portal.acm.org/citation.cfm?id=1374466
104:
92:
55:Noisy version ("Learning Parity with Noise")
364:
350:
249:
264:
375:
316:
71:)), the algorithm is provided with (
13:
14:
399:
320:
258:
237:
183:
177:
148:
142:
1:
230:
336:. You can help Knowledge by
265:Pietrzak, Krzysztof (2012).
110:{\displaystyle b\in \{0,1\}}
79:), where for random boolean
7:
282:10.1007/978-3-642-27660-6_9
218:
10:
404:
315:
39:)) and the assurance that
388:Applied mathematics stubs
332:-related article is a
207:
111:
27:, given some samples (
208:
112:
225:Learning with errors
122:
83:
49:Gaussian elimination
330:applied mathematics
203:
198:
107:
345:
344:
194:
159:
395:
383:Machine learning
366:
359:
352:
324:
317:
286:
285:
271:
262:
256:
255:
253:
241:
212:
210:
209:
204:
202:
201:
195:
192:
160:
157:
116:
114:
113:
108:
21:machine learning
19:is a problem in
403:
402:
398:
397:
396:
394:
393:
392:
373:
372:
371:
370:
313:
290:
289:
269:
263:
259:
242:
238:
233:
221:
197:
196:
191:
189:
165:
164:
156:
154:
132:
131:
123:
120:
119:
84:
81:
80:
57:
17:Parity learning
12:
11:
5:
401:
391:
390:
385:
369:
368:
361:
354:
346:
343:
342:
325:
311:
310:
302:
294:
288:
287:
257:
235:
234:
232:
229:
228:
227:
220:
217:
200:
190:
188:
185:
182:
179:
176:
173:
170:
167:
166:
163:
155:
153:
150:
147:
144:
141:
138:
137:
135:
130:
127:
106:
103:
100:
97:
94:
91:
88:
56:
53:
9:
6:
4:
3:
2:
400:
389:
386:
384:
381:
380:
378:
367:
362:
360:
355:
353:
348:
347:
341:
339:
335:
331:
326:
323:
319:
318:
314:
308:
303:
300:
295:
292:
291:
283:
279:
275:
268:
261:
252:
247:
240:
236:
226:
223:
222:
216:
213:
186:
180:
174:
171:
168:
161:
151:
145:
139:
133:
128:
125:
117:
101:
98:
95:
89:
86:
78:
74:
70:
66:
62:
52:
50:
46:
43:computes the
42:
38:
34:
30:
26:
22:
18:
338:expanding it
327:
312:
273:
260:
239:
214:
118:
76:
72:
68:
64:
60:
58:
40:
36:
32:
28:
24:
16:
15:
276:: 99--114.
377:Categories
251:cs/0010022
231:References
193:otherwise
172:−
90:∈
219:See also
158:if
75:,
63:,
31:,
45:parity
328:This
270:(PDF)
246:arXiv
334:stub
278:doi
379::
272:.
365:e
358:t
351:v
340:.
309:.
301:.
284:.
280::
254:.
248::
187:,
184:)
181:x
178:(
175:f
169:1
162:b
152:,
149:)
146:x
143:(
140:f
134:{
129:=
126:y
105:}
102:1
99:,
96:0
93:{
87:b
77:y
73:x
69:x
67:(
65:ฦ
61:x
41:ฦ
37:x
35:(
33:ฦ
29:x
25:ฦ
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
