29
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Boaz Barak Nov 27 '10 at 4:46
  • $\begingroup$ 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. $\endgroup$ – Gil Kalai Nov 27 '10 at 16:22
31
+200
$\begingroup$

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

$\endgroup$
  • $\begingroup$ yes, Luca, it looks you are correct. $\endgroup$ – Gil Kalai Nov 29 '10 at 5:27

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.