Parity learning is a problem in
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
. 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
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
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")
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
The noisy version of the parity learning problem is conjectured to be hard.
See also
*
Learning with errors
Learning with errors (LWE) is the computational problem of inferring a linear n-ary function f over a finite ring from given samples y_i = f(\mathbf_i) some of which may be erroneous.
The LWE problem is conjectured to be hard to solve, and thus to ...
References
* 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.
* 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, http://portal.acm.org/citation.cfm?id=1374466.
* 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, http://portal.acm.org/citation.cfm?id=1060590.1060603.
Machine learning
{{Mathapplied-stub