<p>Gil, would something like this be a counterexample?</p>

<p>Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.</p>

<p>Then we define $f(x,i):= x_1 \oplus \cdots \oplus x_i$
</p>

<p>Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)</p>

<p>f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual). </p>

CC BY-SA 2.5
2010-11-29T05:27:55.070Z
yes, Luca, it looks you are correct.
Gil Kalai
CC BY-SA 2.5
2010-11-28T22:25:26.840Z
2010-11-28T23:34:18.947Z
2010-11-28T23:34:18.947Z
Luca Trevisan
<p>Let <span class="math-container">$f$</span> be a Boolean function and let's think about f as a function from <span class="math-container">$\{-1,1\}^n$</span> to <span class="math-container">$\{ -1,1 \}$</span>. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These <span class="math-container">$2^n$</span> monomials form a basis to the space of real functions on <span class="math-container">$\{-1,1\}^n$</span>. The sum of the squares of the coefficients is simply <span class="math-container">$1$</span> so <span class="math-container">$f$</span> leads to a probability distribution on square free monomials. Let's call this distribution the F-distribution.</p>

<p>If f can be described by a bounded depth circuit of polynomial size then we know by a theorem of Linial, Mansour and Nisan that the F distribution is concentrated on monomials of <span class="math-container">$\text{polylog } n$</span> size up to almost-exponentially-small weight. This is derived from Hastad switching lemma. (A direct proof would be most desirable.)</p>

<p>What happens when we add mod 2 gates? One example to consider is the function <span class="math-container">$IP_{2n}$</span> on <span class="math-container">$2n$</span> variables which is described as the mod 2 inner product of the first n variables and the last n variables. Here the F-distribution is uniform.</p>

<blockquote>
  <p><strong>Question</strong>: Is the F-distribution of a Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD<span class="math-container">$_2$</span> circuit concentrated (up to
  superpolynomially small error) on <span class="math-container">$o(n)$</span>
  "levels"?</p>
</blockquote>

<p><strong>Remarks</strong>: </p>

<ol>
<li><p>One possible path to a counterexample would be to "glue somehow" various IP<span class="math-container">$_2k$</span> on disjoint sets of variables but I don't see how to do it. Perhaps one should weaken the question and allow assigning some weights to the variables, but I don't see a clear way for doing it either. (So referring to these two matters is also part of what I am asking about.)</p></li>
<li><p>I would speculate that a positive answer to the question, (or to a successful variation) will apply also when you allow mod<span class="math-container">$_k$</span> gates. (So asking the question was motivated by Ryan Williams' recent impressive ACC result.)   </p></li>
<li><p>For MAJORITY the F-distribution is large (1/poly) for every "level".</p></li>
</ol>

<blockquote>
  <p>As shown by Luca, the answer to the question I asked is "no". The question that is left is to propose ways to find properties of the F distributions of Boolean functions that can be described by AND OR and mod 2 gates not shared by MAJORITY. </p>
</blockquote>

<p>An attempt to save the question by talking about MONOTONE functions:</p>

<blockquote>
  <p><strong>Question</strong>: Is the F-distribution of a MONOTONE Boolean function described by
  bounded depth polynomial size AND, OR,
  MOD<span class="math-container">$_2$</span> circuit concentrated (up to
  superpolynomially small error) on <span class="math-container">$o(n)$</span>
  "levels"?</p>
</blockquote>

<p>We may speculate that we can even replace <span class="math-container">$o(n)$</span> by <span class="math-container">$\text{polylog} (n)$</span> so a counterexample for this strong version can be interesting.   </p>

CC BY-SA 2.5
2010-11-27T04:46:54.053Z
It seems a very strong conjecture, would be very interesting if there's evidence it could be true. Is the intuition behind this that for constant depth circuits with mod gates you can either have functions that are very noise insensitive like low degree polynomials, or perfectly random like parity, but it's hard to create something in the middle like majority?
Boaz Barak
CC BY-SA 2.5
2010-11-27T16:22:27.127Z
Dear Boaz, (I would expect a counterexample to the strong suggested statement.) Re: intuition, replace "perfectly random" by "Bernouli-like". As I remember, when you consider a single mod k gate then the F-Distribution is like a certain Bernouli distribution (namely the weight for |S| is like p^|S| (1-p)^{n-|S|} for some p, not necessarily p=1/2. So it looks that small bounded depth circuits with mod k gates manipulate in their F-distrributions such Bernouli distribitions so perhaps the property of "most weights on few levels" (Or some other property of Bernouli distributions) is maintained.
Gil Kalai
<cc.complexity-theory><lower-bounds><circuit-complexity><boolean-functions><fourier-analysis>
Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates
Gil Kalai
# Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

(Asked by: username_0 on 2010-11-26)

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These $2^n$ monomials form a basis to the space of real functions on $\{-1,1\}^n$. The sum of the squares of the coefficients is simply $1$ so $f$ leads to a probability distribution on square free monomials. Let's call this distribution the F-distribution.

If f can be described by a bounded depth circuit of polynomial size then we know by a theorem of Linial, Mansour and Nisan that the F distribution is concentrated on monomials of $\text{polylog } n$ size up to almost-exponentially-small weight. This is derived from Hastad switching lemma. (A direct proof would be most desirable.)

What happens when we add mod 2 gates? One example to consider is the function $IP\_{2n}$ on $2n$ variables which is described as the mod 2 inner product of the first n variables and the last n variables. Here the F-distribution is uniform.

> **Question**: Is the F-distribution of a Boolean function described by
> bounded depth polynomial size AND, OR,
> MOD$\_2$ circuit concentrated (up to
> superpolynomially small error) on $o(n)$
> "levels"?

**Remarks**:

1. One possible path to a counterexample would be to "glue somehow" various IP$\_2k$ on disjoint sets of variables but I don't see how to do it. Perhaps one should weaken the question and allow assigning some weights to the variables, but I don't see a clear way for doing it either. (So referring to these two matters is also part of what I am asking about.)
2. I would speculate that a positive answer to the question, (or to a successful variation) will apply also when you allow mod$\_k$ gates. (So asking the question was motivated by Ryan Williams' recent impressive ACC result.)
3. For MAJORITY the F-distribution is large (1/poly) for every "level".

> As shown by Luca, the answer to the question I asked is "no". The question that is left is to propose ways to find properties of the F distributions of Boolean functions that can be described by AND OR and mod 2 gates not shared by MAJORITY.

An attempt to save the question by talking about MONOTONE functions:

> **Question**: Is the F-distribution of a MONOTONE Boolean function described by
> bounded depth polynomial size AND, OR,
> MOD$\_2$ circuit concentrated (up to
> superpolynomially small error) on $o(n)$
> "levels"?

We may speculate that we can even replace $o(n)$ by $\text{polylog} (n)$ so a counterexample for this strong version can be interesting.

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: It seems a very strong conjecture, would be very interesting if there's evidence it could be true. Is the intuition behind this that for constant depth circuits with mod gates you can either have functions that are very noise insensitive like low degree polynomials, or perfectly random like parity, but it's hard to create something in the middle like majority?  
> **username_0**: Dear Boaz, (I would expect a counterexample to the strong suggested statement.) Re: intuition, replace "perfectly random" by "Bernouli-like". As I remember, when you consider a single mod k gate then the F-Distribution is like a certain Bernouli distribution (namely the weight for |S| is like p^|S| (1-p)^{n-|S|} for some p, not necessarily p=1/2. So it looks that small bounded depth circuits with mod k gates manipulate in their F-distrributions such Bernouli distribitions so perhaps the property of "most weights on few levels" (Or some other property of Bernouli distributions) is maintained.  

---

## 1 answers

### Answer by username_2 on 2010-11-28. Score: 33 | Accepted answer

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x\_1,\ldots ,x\_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x\_1 \oplus \cdots \oplus x\_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x\_1 \oplus \cdots \oplus x\_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).

> **Comments:**
> **username_0**: yes, Luca, it looks you are correct.  

---

