Was ist die Tendenz von zufälligen Polynomen mit niedrigem Grad über GF (2)?

13

Ich habe eine Frage zu Polynomen niedrigen Grades und zur Wahrscheinlichkeit: Was ist das (assyptotische Verhalten der) Wahrscheinlichkeit, dass ein zufälliges * Polynom über GF (2) mit Variablen des Grades und n einen .d B i a s ( p ) | Pr x { 0 , 1 } n ( p ( x ) = 0 ) - Pr x { 0 , 1 } n ( p ( x ) = 1 ) | > ϵpdbias(p)|Prx{0,1}n(p(x)=0)Prx{0,1}n(p(x)=1)|>ϵ

* Wenn ich ein zufälliges Polynom mit den Variablen degree d und n schreibe , können Sie sich jedes Monom mit dem Gesamtgrad d vorstellen, das mit der Wahrscheinlichkeit 1/2 ausgewählt wurde.

Das einzig Relevante, das ich kenne, ist eine Variante von Schwartz-Zippel, die besagt, dass wenn das Polynom nicht konstant ist, seine Vorspannung höchstens 1-2 ^ {1-d} beträgt 121d. Daher ist für ϵ=121d die Wahrscheinlichkeit genau 1/2(n1)++(nd) wobei dies die Wahrscheinlichkeit ist, dass p ist eine Konstante. Leider ist dieses ϵ ziemlich groß.

Avishay Tal
quelle
1
Was ist f in Bias (f)?
Tyson Williams

Antworten:

5

Die Arbeit "Random low-degree polynoms are hard to approximate" von Ben-Eliezer, Hod und Lovett beantwortet Ihre Frage. Sie zeigen starke Grenzen für die Korrelation von zufälligen Polynomen des Grades d mit Polynomen des Grades höchstens d1 , indem sie die Verzerrung von zufälligen Polynomen analysieren. Siehe ihr Lemma 2: Die Verzerrung eines Polynoms zufälligen Grades d (bis zu einem d , das in n linear ist n) beträgt höchstens 2Ω(n/d) , außer mit Wahrscheinlichkeit 2Ω((nd)) .

David
quelle
Hallo @david, deine Antwort war sehr hilfreich. Ich wollte dich etwas per E-Mail fragen, kannst du mir eine Nachricht schicken?
Avishay Tal
5

Ihre Frage ist gleichbedeutend mit den Grenzwerten für die Gewichtsverteilung von Reed-Muller-Codes. Das Verständnis der Gewichtsverteilung von Reed-Muller-Codes ist eine alte und herausfordernde Frage in der Codierungstheorie, und es sind mehrere interessante Ergebnisse darüber bekannt (die Gewichtsverteilung ist nur für und vollständig verstanden ). Als guter Ausgangspunkt siehe "Gewichtsverteilung und Listendecodierungsgröße von Reed-Muller-Codes" von Tali Kaufman, Shachar Lovett, Ely Porat und die darin enthaltenen Referenzen.d=1d=2

MCH
quelle