Résultats des limites inférieures / dureté Noisy Parity (LWE)

Quelques antécédents:

Je suis intéressé à trouver des limites inférieures (ou des résultats de dureté) "moins connues" pour le problème d'apprentissage avec des erreurs (LWE), et des généralisations de celui-ci comme l'apprentissage avec des erreurs sur des anneaux. Pour des définitions spécifiques, etc., voici une belle enquête de Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

Le type standard d'hypothèse de type (R) LWE est via la réduction (peut-être, quantique) au problème de vecteur le plus court sur des réseaux (peut-être, idéaux). La formulation habituelle de SVP est connue pour être NP-difficile, et on croit qu'il est difficile d'approcher les petits facteurs polynomiaux. (Connexes: Il est difficile d'approximer CVP à l'intérieur / presque-polynômes / facteurs: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) J'ai également entendu dire que (en termes d'algorithmes quantiques) l'approximation de certains problèmes de réseau (comme SVP) à de petits facteurs d'approximation polynomiale est liée au problème de sous-groupe caché non abélien (qui est considéré comme difficile pour ses propres raisons), bien que je n'ai jamais vu de source formelle explicite pour cela.

Cependant, je suis plus intéressé par les résultats de dureté (de tout type) qui résultent du problème de parité bruyante de la théorie de l'apprentissage. Il peut s'agir de résultats de dureté de classe de complexité, de limites inférieures algorithmiques concrètes, de limites de complexité d'échantillons ou même de limites inférieures de taille d'épreuve (par exemple, Résolution). Il est connu (peut-être évident) que le LWE peut être considéré comme une généralisation du problème de parité bruyante / parité d'apprentissage avec bruit (LPN), qui (d'après Google) semble avoir été utilisé pour réduire la dureté dans des domaines comme la théorie du codage et le PAC. apprentissage.

En regardant autour de moi, je n'ai trouvé que des rebonds supérieurs (légèrement sous-exponentiels) sur le problème LPN, par exemple http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Question:

Je sais que LPN est CROYE DUR dans la communauté d'apprentissage. Ma question est: pourquoi?

Est-ce parce que tout le monde a vraiment essayé, mais personne n'a encore trouvé un bon algorithme? Y a-t-il des limites inférieures connues de la variété en italique ci-dessus (ou d'autres que j'ai omises)?

Si la réponse est très claire, un résumé succinct de ce qui est connu et / ou des références à des sondages / notes de cours serait parfait.

Si beaucoup de choses sont inconnues, plus il y a de papiers "à la pointe de la technologie", mieux c'est. :) (Merci d'avance!)

Le problème LPN est en effet considéré comme difficile, mais comme la plupart des problèmes que nous croyons difficiles, la principale raison est que de nombreuses personnes intelligentes ont essayé de trouver un algorithme efficace et ont échoué.

La meilleure "preuve" de la dureté du LPN vient de la dimension de requête statistique élevée du problème de parité. Les requêtes statistiques capturent la plupart des algorithmes d'apprentissage connus, à l'exception de l'élimination gaussienne (qui échoue chaque fois que du bruit est introduit), du hachage et des techniques similaires à ces deux. Il est difficile de concevoir des algorithmes de requête non statistique, et c'est le principal goulot d'étranglement. Une autre preuve de la dureté de LPN est sa relation avec d'autres problèmes difficiles (comme LWE, SVP comme vous l'avez souligné).

Pour la dureté SQ, voici le lien vers le papier de Kearns ('98).

Pour progresser sur les limites supérieures de ce problème, il y a plusieurs résultats:

• $2^N$$2^{n / \log n}$
• $O(2^{n / \log\log n})$$O(n^{1 + \epsilon})$
• $k$$\approx O(n^{0.5 k})$$O(n^k)$$O(n^k)$$\eta$$1/2$
• $\approx O(n^{0.8 k})$