13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is f in bias(f)? $\endgroup$ – Tyson Williams Jun 24 '12 at 14:47
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hi @david, your answer was very helpful. I wanted to ask you something via e-mail, can you send me a message? $\endgroup$ – Avishay Tal Oct 11 '13 at 10:46
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.