Jaka jest tendencja do losowych wielomianów o niskim stopniu nad GF (2)?

13

pdbias(p)|Prx{0,1}n(p(x)=0)Prx{0,1}n(p(x)=1)|>ϵ

* Gdy piszę losowy wielomian o stopniu d a n zmiennych, można myśleć o każdy jednomianów całkowitego stopnia d pobrane z prawdopodobieństwem 1/2.

Jedyną istotną rzeczą, jaką znam, jest wariant Schwartza-Zippla, który stwierdza, że ​​jeśli wielomian jest niestały, wówczas jego odchylenie wynosi co najwyżej 121d . Stąd dla ϵ=121d prawdopodobieństwo wynosi dokładnie 1/2(n1)++(nd) gdzie jest to prawdopodobieństwo, że p jest stała. Niestety ten ϵ jest dość duży.

Avishay Tal
źródło
1
Co to jest F w stronniczości (f)?
Tyson Williams

Odpowiedzi:

5

Artykuł „Losowe wielomiany niskiego stopnia są trudne do przybliżenia” autorstwa Ben-Eliezera, Hoda i Lovetta odpowiada na twoje pytanie. Wykazują silne granice korelacji losowych wielomianów stopnia z wielomianami stopnia co najwyżej , analizując tendencyjność losowych wielomianów. Zobacz ich Lemat 2: błąd systematyczny wielomianu stopnia (do pewnego który jest liniowy w ) wynosi co najwyżej , z wyjątkiem prawdopodobieństwa .dd1ddn2Ω(n/d)2Ω((nd))

David
źródło
Cześć @david, twoja odpowiedź była bardzo pomocna. Chciałem cię o coś zapytać przez e-mail, czy możesz wysłać mi wiadomość?
Avishay Tal,
5

Twoje pytanie jest równoważne ograniczeniom ogona w rozkładzie masy kodów Reeda-Mullera. Zrozumienie rozkładu ciężaru kodów Reeda-Mullera jest starym i trudnym pytaniem w teorii kodowania, i wiadomo o nim kilka interesujących wyników (rozkład masy jest całkowicie zrozumiały tylko dla i ). Jako doskonały punkt wyjścia, patrz „Rozkład masy i rozmiar dekodowania kodów kodów Reeda-Mullera” Tali Kaufmana, Shachara Lovetta, Ely'ego Porata i odnośniki w nim zawarte.d=1d=2

MCH
źródło