7

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.

Community
  • 1
Igor Shinkar
  • 1,927
  • 11
  • 21
  • 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. – Tsuyoshi Ito Oct 23 '14 at 22:45
  • @TsuyoshiIto I am interested in both distributions. – Igor Shinkar Oct 23 '14 at 22:57
  • 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. – Igor Shinkar Oct 23 '14 at 23:01
  • 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$. – Yuval Filmus Oct 24 '14 at 01:15
  • @YuvalFilmus, if we consider the uniform distribution over all $n$-bit functions of degree $\leq d$, then "high probability" is w.r.t. $n$. For example for $d=1$ we have $n$ dictators, $n$ anti-dictators and 2 constant function. So with probability $n/(n+1)$ a random function is balanced.

    And if we consider the variant in Remark 1, then "high probability" is w.r.t. $d$.

     – Igor Shinkar Oct 24 '14 at 17:45
  • Call a Boolean function $d$-critical if it has degree $d$ and depends on the maximal number of variables. The limiting distribution of your distribution is supported on the finitely many $d$-critical functions, so we can rephrase your question as: are all $d$-critical functions balanced? – Yuval Filmus Oct 24 '14 at 19:10
  • I don't understand. Why is the limit supported on $d$-critical function? i.e., why is it true that most functions are $d$-critical? – Igor Shinkar Oct 24 '14 at 21:50
  • 1
    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. – Yuval Filmus Oct 26 '14 at 07:43
  • Right! I see your point... – Igor Shinkar Oct 26 '14 at 13:58

0 Answers0