Jump to content

Parity learning

From Wikipedia, the free encyclopedia

Parity learning is a problem in machine learning. An algorithm that solves this problem must find a function ƒ, given some samples (x, ƒ(x)) and the assurance that ƒ computes the parity of bits at some fixed locations. The samples are generated using some distribution over the input. The problem is easy to solve using Gaussian elimination provided that a sufficient number of samples (from a distribution which is not too skewed) are provided to the algorithm.

Noisy version ("Learning Parity with Noise")

[edit]

In Learning Parity with Noise (LPN), the samples may contain some error. Instead of samples (x, ƒ(x)), the algorithm is provided with (x, y), where for random boolean b∈{0,1}

y={f(x),if b1−f(x),otherwise

The noisy version of the parity learning problem is conjectured to be hard[1] and is widely used in cryptography.[2]

See also

[edit]

References

[edit]
  1. ↑ Wasserman, Hal; Kalai, Adam; Blum, Avrim (2000-10-15). "Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model". arXiv:cs/0010022.
  2. ↑ Pietrzak, Krzysztof (2012). "Cryptography from Learning Parity with Noise" (PDF). SOFSEM 2012: Theory and Practice of Computer Science. Lecture Notes in Computer Science. Vol. 7147. pp. 99–114. doi:10.1007/978-3-642-27660-6_9. ISBN 978-3-642-27659-0. {{cite book}}: |journal= ignored (help)