What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree?

More specifically, is it true that if we take a uniformly random function $f:\{0,1\}^n \to \{0,1\}$ among those that can be represented as a real polynomial of degree $\leq d$, then $\mathbb{E}[f]$ will be close to 0.5 with high probability?

Remark 1: Alternatively, it also makes sense to consider the following distribution: when choosing a random function of degree $d$, identify functions that are equivalent up to renaming coordinates, so a random function is in fact a random equivalence class.

Remark 2: This question is somewhat related: Random functions of low degree as a real polynomial.

  • $\begingroup$ Which probability distribution are you asking about? Uniform among the functions from {0,1}^n to {0,1} with polynomial degree at most d, or uniform among the coordinate-renaming equivalent classes of such functions? Without Remark 1, I would have assumed the former, but after reading Remark 1, I am no longer sure. $\endgroup$ Oct 23, 2014 at 22:45
  • $\begingroup$ @TsuyoshiIto I am interested in both distributions. $\endgroup$ Oct 23, 2014 at 22:57
  • $\begingroup$ Note that if one can prove that for any $x,y \in \{0,1\}^n$ the values $f(x)$ and $f(y)$ are independent, then we will get concentration using Chebyshev inequality. $\endgroup$ Oct 23, 2014 at 23:01
  • $\begingroup$ What do you mean by "high probability"? Every polynomial of degree at most $d$ depends on at most $d2^d$ variables (or so), so for $n \geq d2^d$ the probability won't depend on $n$. The Kindler–Safra theorem shows that the same holds even if your function is only close to degree $d$. $\endgroup$ Oct 24, 2014 at 1:15
  • 1
    $\begingroup$ Following your example for $d=1$, a function which depends on $k$ variables has $\Theta(n^k)$ "manifestations" (the constant depends on the number of symmetries), so in the limit we will only see the functions depending on the most arguments, just as for $d=1$ we only see dictators and anti-dictators. $\endgroup$ Oct 26, 2014 at 7:43


Your Answer

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

Browse other questions tagged or ask your own question.