¿Cuál es el sesgo de los polinomios aleatorios con bajo grado sobre GF (2)?

$p$$\le d$$bias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon$

* Cuando escribo polinomios aleatorios con grados yn variables, puedes pensar en cada monomio de grado total elegido con probabilidad 1/2.$\le d$$\le d$

Lo único relevante que conozco es una variante de Schwartz-Zippel que establece que si el polinomio no es constante, su sesgo es como máximo . Por lo tanto, para la probabilidad es exactamente 1 / {2 ^ {{n \ choose 1} + \ ldots + {n \ choose d}}} donde esta es la probabilidad de que p sea una constante. Desafortunadamente, este \ epsilon es bastante grande.$1-2^{1-d}$$\epsilon=1-2^{1-d}$$1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$$p$$\epsilon$

El artículo "Los polinomios aleatorios de bajo grado son difíciles de aproximar" por Ben-Eliezer, Hod y Lovett responde a su pregunta. Muestran fuertes límites en la correlación de polinomios aleatorios de grado con polinomios de grado como máximo d - 1 , analizando el sesgo de polinomios aleatorios. Vea su Lema 2: el sesgo de un polinomio aleatorio de grado d (hasta algunos d que es lineal en n ) es como máximo 2 - Ω ( n / d ) , excepto con probabilidad 2 - Ω ( $d$$d-1$$d$$d$$n$$2^{-\Omega(n / d)}$.$2^{-\Omega\Big(\binom{n}{\le d}\Big)}$

Su pregunta es equivalente a los límites de cola en la distribución de peso de los códigos Reed-Muller. La distribución del peso comprensión de los códigos Reed-Muller es un viejo y desafiando a la pregunta en la teoría de codificación, y se conocen varios resultados interesantes al respecto (la distribución del peso es totalmente conocido sólo para y D = 2 ). Como un excelente punto de partida, vea "Distribución de peso y tamaño de decodificación de listas de códigos Reed-Muller" por Tali Kaufman, Shachar Lovett, Ely Porat, y las referencias allí.$d=1$$d=2$