<p>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)}$.</p>

CC BY-SA 3.0
2013-10-11T10:46:58.223Z
Hi @david, your answer was very helpful. I wanted to ask you something via e-mail, can you send me a message?
Avishay Tal
CC BY-SA 3.0
2012-06-22T10:50:52.390Z
2012-06-22T10:50:52.390Z
david
<p>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.</p>

CC BY-SA 3.0
2012-06-21T18:04:56.753Z
2012-06-21T18:23:52.143Z
2012-06-21T18:23:52.143Z
Mahdi Cheraghchi
<p>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$.</p>

<p>*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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-24T14:47:21.400Z
What is f in bias(f)?
Tyson Williams
<randomness><pr.probability><algebra><polynomials>
What's the bias of random polynomials with low degree over GF(2)?
Avishay Tal
# What's the bias of random polynomials with low degree over GF(2)?

(Asked by: username_0 on 2012-06-21)

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.

**Tags:** randomness, pr.probability, algebra, polynomials

> **Comments:**
> **username_1**: What is f in bias(f)?  

---

## 2 answers

### Answer by username_2 on 2012-06-22. Score: 6 | Accepted answer

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)}$.

> **Comments:**
> **username_0**: Hi @username_2, your answer was very helpful. I wanted to ask you something via e-mail, can you send me a message?  

---

### Answer by username_3 on 2012-06-21. Score: 6

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.


---

