Qual é o viés de polinômios aleatórios com baixo grau sobre GF (2)?

Eu tenho uma pergunta sobre polinômios de baixo grau e probabilidade: Qual é a (comportamento assiptótico da) probabilidade de que um polinômio * aleatório, , acima de GF (2), com grau e n variáveis ​​tenha .≤ d b i a s ( p ) ≜ | Pr x ∈ { 0 , 1 } n ( p ( x ) = 0 ) - Pr x ∈ { 0 , 1 } n ( p ( x ) = 1 ) | > $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$

* Quando estou escrevendo polinômio aleatório com variáveis ​​de grau $\le d$ e n, você pode pensar em cada monômio do grau total $\le d$ escolhido com probabilidade 1/2.

A única coisa relevante que conheço é uma variante de Schwartz-Zippel que afirma que, se o polinômio é inconstante, seu viés é no máximo . Portanto, para a probabilidade é exatamente que esta é a probabilidade de ser uma constante. Infelizmente, esse é bastante grande.$1-2^{1-d}$ 1 / 2 ($\epsilon=1-2^{1-d}$ p$1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$$p$$\epsilon$

O artigo "Polinômios aleatórios de baixo grau são difíceis de aproximar" de Ben-Eliezer, Hod e Lovett responde à sua pergunta. Eles mostram fortes limites na correlação de polinômios aleatórios de grau com polinômios de grau no máximo , analisando o viés de polinômios aleatórios. Veja o Lema 2: o viés de um polinômio aleatório de grau (até alguns que é linear em ) é no máximo , exceto com probabilidade .d - 1 d d n 2 - Ω ( n / d ) 2 - Ω $d$$d-1$$d$$d$$n$$2^{-\Omega(n / d)}$$2^{-\Omega\Big(\binom{n}{\le d}\Big)}$

Sua pergunta é equivalente a limites de cauda na distribuição de peso dos códigos Reed-Muller. Distribuição de peso compreensão de códigos Reed-Muller é uma questão de idade e desafiando em teoria de codificação, e vários resultados interessantes são conhecidos sobre ele (a distribuição de peso é completamente entendido apenas para e ). Como um excelente ponto de partida, consulte "Distribuição de peso e tamanho de decodificação de lista de códigos Reed-Muller", de Tali Kaufman, Shachar Lovett, Ely Porat e as referências nele contidas.$d=1$$d=2$