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!)
źródło