What's the bias of random polynomials with low degree over GF(2)?

Question

I have a question concerning low-degree polynomials and probability: What is the (assyptotic behavior of the) probability that a random* polynomial, $p$, over GF(2), with degree $\le d$ and n variables has $bias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon$.

*When I'm writing random polynomial with degree $\le d$ and n variables, you can think of each monomials of total degree $\le d$ picked with probability 1/2.

The only relevant thing I know is a variant of Schwartz-Zippel that states that if the polynomial is nonconstant then its bias is at most $1-2^{1-d}$. Hence, for $\epsilon=1-2^{1-d}$ the probaiblity is exactly $1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$ where this is the probability that $p$ is a constant. Unfortunately, this $\epsilon$ is quite big.

Answer 1

The paper "Random low-degree polynomials are hard to approximate" by Ben-Eliezer, Hod, and Lovett answers your question. They show strong bounds on the correlation of random polynomials of degree $d$ with polynomials of degree at most $d-1$, by analyzing the bias of random polynomials. See their Lemma 2: the bias of a random degree-$d$ polynomial (up to some $d$ that is linear in $n$) is at most $2^{-\Omega(n / d)}$, except with probability $2^{-\Omega\Big(\binom{n}{\le d}\Big)}$.

Answer 2

Your question is equivalent to tail bounds on the weight distribution of Reed-Muller codes. Understanding weight distribution of Reed-Muller codes is an old and challenging question in coding theory, and several interesting results are known about it (the weight distribution is completely understood only for $d=1$ and $d=2$). As a great starting point, see "Weight Distribution and List-Decoding Size of Reed-Muller Codes" by Tali Kaufman, Shachar Lovett, Ely Porat, and the references therein.