Noisy Parity (LWE) lower bounds/hardness results

Question

Some background:

I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over Rings. For specific definitions, etc., here is a nice survey by Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

The standard type of (R)LWE-style assumption is via (perhaps, quantum) reduction to the Shortest Vector Problem on (perhaps, ideal) lattices. The usual formulation of SVP is known to be NP-hard, and it's BELIEVED to be hard to approximate to small polynomial factors. (Related: It's hard to approximate CVP to within /almost-polynomial/ factors: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) I've also heard it mentioned that (in terms of quantum algorithms) approximating certain lattice problems (like SVP) to small polynomial approximation factors is related to the non-Abelian hidden subgroup problem (which is believed to be hard for its own reasons), though I've never seen an explicit, formal source for this.

I'm more interested, however, in hardness results (of any type) that come as a result of the Noisy Parity problem from Learning Theory. These could be complexity class hardness results, concrete algorithmic lower bounds, sample complexity bounds, or even proof size lower bounds (e.g. Resolution). It is known (perhaps, obvious) that LWE can be viewed as a generalization of the Noisy Parity/Learning Parity with Noise (LPN) problem, which (from Googling) appears to have been used in hardness reductions in areas like coding theory and PAC learning.

From looking around myself, I've only found (mildly subexponential) UPPER BOUNDS on the LPN problem, e.g. http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Question:

I know LPN is BELIEVED HARD in the learning community. My question is: Why?

Is it because everyone tried really hard, but no one's found a good algorithm yet? Are there known lower bounds of the italicized variety above (or others I left out)?

If the answer is very clear-cut, a succinct summary of what's known and/or references to surveys/lecture notes would be great.

If much is unknown, the more "state-of-the-art" papers, the better. :) (Thanks ahead of time!)

Answer 1

The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.

The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem. Statistical queries capture most known learning algorithms, except for gaussian elimination (which fails whenever noise is introduced), hashing, and techniques similar to these two. It is hard to design non statistical-query algorithms, and this is the main bottleneck. Other evidence of LPN's hardness is its relationship to other hard problems (like LWE, SVP as you've pointed out).

For the SQ-hardness, here is the link to Kearns's ('98) paper.

For progress on the upper bounds on this problem, there are several results:

• Probably the most famous is the Blum-Kalai-Wasserman ('00) result which beats the $2^N$ SQ barrier by a little, giving an algorithm that runs in time $2^{n / \log n}$. (link)
• Lyubashevsky ('05) found an algorithm with worse running time $O(2^{n / \log\log n})$ but better sample complexity of $O(n^{1 + \epsilon})$. (link)
• In the sparse case, where we know the parity is on $k$ variables, Grigorescu-Reyzin-Vempala ('11) gave a $\approx O(n^{0.5 k})$ algorithm, beating the $O(n^k)$ brute-force. However, this bound decays toward $O(n^k)$ as the noise rate $\eta$ approaches $1/2$. (link)
• Valiant ('12) recently gave a $\approx O(n^{0.8 k})$ algorithm for the sparse case. This bound is stronger because it does not decay in the exponent with the noise rate (unlike the GRV result). (link)