Parity learning is a problem in machine Learning

Machine learning

Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...

. An algorithm claiming to solve this problem must try to guess the function ƒ(x), given some samples (x, ƒ(x)) and the assurance that ƒ computes the parity

Parity function

In Boolean algebra, a parity function is a Boolean function whose value is 1 if the input vector has an odd number of ones.The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.-Definition:...

 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

Gaussian elimination

In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...

provided that enough number of samples (from a distribution which is not too skew) are provided to the algorithm.

Noisy version

In this version, the samples may contain some error. Instead of samples (x, ƒ(x)), the algorithm is provided with (x, y), where y = 1 − ƒ(x) with some small probability.