4
$\begingroup$

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.
$\endgroup$

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.