Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the problem (they are not SQ-learnable even if the parity is assumed to be sparse).

I'm interested in a noise rate which decays with $n$, the number of features, and I want to know where the known easiness threshold is for this problem.

Specific notes:

  • LPN is easy with noise rate $\eta = O(1/n)$, because drawing $O(n)$ samples will with good probability produce $O(1)$ noisy examples.
  • It seems like it should still be hard for $\eta = O(1/\log n)$ and even $O(1/\sqrt{n})$.
  • Is it known to be easy for any $\eta = \omega(1/n)$?
  • LPN is equivalent to decoding random linear codes, but I have not heard of any work with sublinear noise rates for coding theory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.