Wyniki dla niższych granic / twardości w Noisy Parity (LWE)

Niektóre tło:

Chciałbym znaleźć „mniej znane” dolne granice (lub wyniki twardości) dla problemu Uczenie się z błędami (LWE) i ich uogólnienia, takie jak Uczenie się z błędami przez pierścienie. W celu uzyskania szczegółowych definicji itp. Oto miła ankieta przeprowadzona przez Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

Standardowym rodzajem założenia w stylu (R) LWE jest redukcja (być może kwantowa) do problemu najkrótszego wektora na (być może idealnych) sieciach. Wiadomo, że zwykły preparat SVP jest trudny do NP i UWAŻA, że trudno jest go przybliżyć do niewielkich czynników wielomianowych. (Powiązane: Trudno jest zbliżyć CVP do wewnątrz / prawie-wielomianu / czynników: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) Słyszałem też, że wspomniało (o algorytmach kwantowych) przybliżanie niektórych problemów z siecią (np. SVP) do małych wielomianowych czynników aproksymacyjnych jest związane z nieabelowym problemem ukrytej podgrupy (który uważa się za trudny z własnych powodów), chociaż nigdy nie widziałem wyraźnego, formalnego źródła tego.

Bardziej interesują mnie jednak wyniki twardości (dowolnego rodzaju), które powstają w wyniku problemu Noisy Parity z teorii uczenia się. Mogą to być wyniki twardości klasy złożoności, konkretne algorytmiczne dolne granice, przykładowe granice złożoności, a nawet dolne granice wielkości dowodu (np. Rozdzielczość). Wiadomo (być może oczywiste), że LWE może być postrzegane jako uogólnienie problemu Noisy Parity / Learning Parity with Noise (LPN), który (od Googlinga) wydaje się być wykorzystywany do obniżania twardości w obszarach takich jak teoria kodowania i PAC uczenie się.

Rozglądając się wokół siebie, znalazłem (nieznacznie podwykładnicze) GÓRNE BOUNDS dotyczące problemu LPN, np. Http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Pytanie:

Wiem, że LPN jest WIERZĄCY w społeczności uczącej się. Moje pytanie brzmi: dlaczego?

Czy to dlatego, że wszyscy bardzo się starali, ale nikt jeszcze nie znalazł dobrego algorytmu? Czy istnieją znane dolne granice odmiany wyróżnionej kursywą powyżej (lub inne, które pominąłem)?

Jeśli odpowiedź jest bardzo jednoznaczna, świetne byłoby zwięzłe streszczenie tego, co wiadomo i / lub odniesienia do ankiet / notatek z wykładów.

Jeśli wiele jest nieznanych, im więcej „najnowocześniejszych” artykułów, tym lepiej. :) (Dzięki z góry!)

Uważa się, że problem LPN jest trudny, ale podobnie jak większość problemów, które uważamy za trudne, głównym powodem jest to, że wielu inteligentnych ludzi próbowało znaleźć wydajny algorytm i nie udało się.

Najlepsze „dowody” na twardość LPN pochodzą z wysokiego wymiaru zapytania statystycznego dotyczącego problemu parzystości. Zapytania statystyczne wychwytują najbardziej znane algorytmy uczenia się, z wyjątkiem eliminacji gaussowskiej (która kończy się niepowodzeniem po wprowadzeniu hałasu), mieszania i technik podobnych do tych dwóch. Trudno jest zaprojektować algorytmy nie będące statystycznymi zapytaniami i jest to główne wąskie gardło. Innym dowodem twardości LPN jest jego związek z innymi trudnymi problemami (takimi jak LWE, SVP, jak wskazałeś).

Dla twardości SQ tutaj jest link do pracy Kearnsa ('98).

W przypadku postępów w górnych granicach tego problemu istnieje kilka wyników:

• $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})$