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

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

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

<p>Remark 2: This question is somewhat related:  <a href="https://cstheory.stackexchange.com/questions/18727/random-functions-of-low-degree-as-a-real-polynomial">Random functions of low degree as a real polynomial</a>.</p>

CC BY-SA 3.0
2014-10-23T22:45:38.720Z
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
CC BY-SA 3.0
2014-10-23T22:57:27.940Z
@TsuyoshiIto I am interested in both distributions.
Igor Shinkar
CC BY-SA 3.0
2014-10-23T23:01:04.877Z
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
CC BY-SA 3.0
2014-10-24T01:15:19.463Z
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
CC BY-SA 3.0
2014-10-24T17:45:43.360Z
@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
CC BY-SA 3.0
2014-10-24T19:10:41.547Z
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
CC BY-SA 3.0
2014-10-24T21:50:48.213Z
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
CC BY-SA 3.0
2014-10-26T07:43:01.667Z
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
CC BY-SA 3.0
2014-10-26T13:58:50.817Z
Right! I see your point...
Igor Shinkar
<boolean-functions><randomness><bounded-degree>
Bias of a random boolean low degree polynomial
Igor Shinkar
# Bias of a random boolean low degree polynomial

(Asked by: username_0 on 2014-10-23)

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](https://cstheory.stackexchange.com/questions/18727/random-functions-of-low-degree-as-a-real-polynomial).

**Tags:** boolean-functions, randomness, bounded-degree
> **Comments:**
> **username_1**: 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.  
> **username_0**: @TsuyoshiIto I am interested in both distributions.  
> **username_0**: 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.  
> **username_2**: 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$.  
> **username_0**: @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$.  
> **username_2**: 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?  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: Right! I see your point...  

---

## 0 answers

