<p>There are several ways to understand the question according to the precise meaning of "small size" and "concentrate." </p>

<p>1) If you consider Boolean functions so that $1-o(1)$ of their l-2 norm is concentrated on small sized $S$ then the answer is no - the majority function is an example such that $1-o(1)$ of the l-2 norm is on bounded sets and is not in ${\rm AC^0}$.</p>

<p>2) There is a theorem of Bourgain that if the concentration is well above that of the majority function then the function is approximately a Junta, and thus depends on O(1) variables.</p>

<p>3) You can ask that the total influence which is expectation of |S| with respect to the distribution described by $\hat f^2(S)$ is small. For functions in $AC^0$ the total influence is at most ${\rm polylog} (n)$. If the total influence is O(1) then the function is close to a Junta, namely depending on O(1) variables.</p>

<p>4) If the total influence is $O(\log n)$ it is possible but not known that the function is close to a function in $AC^0$. </p>

<p>5) If the total influence is $O(polylog (n))$ then another possibility is a function of bounded depth and $n^{polylog (n)}$ size. It is possible, but unknown, that every function of total influence polylog (n) is close to such a function.  </p>

CC BY-SA 3.0
2013-01-02T10:18:29.860Z
2013-01-02T11:08:38.467Z
2013-01-02T11:08:38.467Z
Gil Kalai
<p>No. Consider the following function on $\{0,1\}^n$:
$$ f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}). $$
Clearly this function is hard for AC<sup>0</sup>. On the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.</p>

<p>If you want a balanced counterexample, consider
$$ g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus 
\cdots \oplus x_{n-1})\right]. $$
This function is almost always equal to $x_0$, so almost all of its Fourier spectrum is on the first two levels.</p>

CC BY-SA 3.0
2012-09-29T18:02:40.677Z
Do you have any robust examples where the function can't be approximated in AC0?
Mahdi Cheraghchi
CC BY-SA 3.0
2012-09-29T23:00:20.670Z
A function concentrated on the first $O(1)$ levels is always close to a function depending on $O(1)$ inputs, so if we're interested in only $O(1)$ levels, then there are no robust examples.
Yuval Filmus
CC BY-SA 3.0
2015-10-10T16:20:44.933Z
@Arul A Fourier level consists of all Fourier coefficients corresponding to sets of a given size. We think of them as ordered in increasing order of size. As for why this function is hard for AC0, this is an exercise. Hint: parity is hard for AC0.
Yuval Filmus
CC BY-SA 3.0
2012-09-29T05:09:30.273Z
2012-09-29T05:09:30.273Z
Yuval Filmus
<p>Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ? </p>

CC BY-SA 3.0
2012-09-28T12:49:42.027Z
This question sounds interesting, though I lack some of the background in fourier analysis. I would appreciate references to related literature.
Markus
CC BY-SA 3.0
2012-09-28T14:06:10.190Z
@Markus: this book 2.0 by Ryan O'Donnell is an excellent reference: http://www.contrib.andrew.cmu.edu/~ryanod/
Alessandro Cosentino
CC BY-SA 3.0
2012-09-28T22:42:12.333Z
almost the converse to [Linial, Mansour, Nissan 1993](http://dl.acm.org/citation.cfm?id=174138)? aaronsons result, [counterexample to generalized Linial-Nissan](http://www.scottaaronson.com/papers/glnfalse.pdf) seems close? but imho theres got to be a way to generalize the 1993 result somehow... maybe in a big way....
vzn
CC BY-SA 3.0
2012-10-04T02:42:49.877Z
another similar idea instead of AC^0, harder to disprove, would be depth unlimited but total gate limited circuits bounded by some "small" function say polynomial etc...? also afaik the relation between monotone circuits and fourier coefficients is not so well known...?
vzn
CC BY-SA 3.0
2012-10-04T02:49:06.653Z
see also [polylogarithmic independence fools AC^0 circuits](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.7081) by braverman
vzn
CC BY-SA 3.0
2012-10-14T10:24:42.397Z
@vzn Thanks for the additional resource suggestions.
Stattrav
CC BY-SA 3.0
2012-10-14T16:26:47.033Z
further thought it seems to be related to the complexity of computing the parity fn of subsets of input variables. see ch2 of juknas book, _boolean fn complexity, advances and frontiers_
vzn
<cc.complexity-theory><circuit-complexity><boolean-functions><fourier-analysis>
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Stattrav
# Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

(Asked by: username_0 on 2012-09-28)

Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: This question sounds interesting, though I lack some of the background in fourier analysis. I would appreciate references to related literature.  
> **username_2**: @Markus: this book 2.0 by Ryan O'Donnell is an excellent reference: http://www.contrib.andrew.cmu.edu/~ryanod/  
> **username_3**: almost the converse to [Linial, Mansour, Nissan 1993](http://dl.acm.org/citation.cfm?id=174138)? aaronsons result, [counterexample to generalized Linial-Nissan](http://www.scottaaronson.com/papers/glnfalse.pdf) seems close? but imho theres got to be a way to generalize the 1993 result somehow... maybe in a big way....  
> **username_3**: another similar idea instead of AC^0, harder to disprove, would be depth unlimited but total gate limited circuits bounded by some "small" function say polynomial etc...? also afaik the relation between monotone circuits and fourier coefficients is not so well known...?  
> **username_3**: see also [polylogarithmic independence fools AC^0 circuits](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.7081) by braverman  
> **username_0**: @vzn Thanks for the additional resource suggestions.  
> **username_3**: further thought it seems to be related to the complexity of computing the parity fn of subsets of input variables. see ch2 of juknas book, _boolean fn complexity, advances and frontiers_  

---

## 2 answers

### Answer by username_5 on 2012-09-29. Score: 19 | Accepted answer

No. Consider the following function on $\{0,1\}^n$:
$$ f(x) = x\_0 \land \cdots \land x\_{n-\sqrt{n}-1} \land (x\_{n-\sqrt{n}} \oplus \cdots \oplus x\_{n-1}). $$
Clearly this function is hard for AC0. On the other hand, the function is almost constant, so almost all of its Fourier spectrum is on the first level.

If you want a balanced counterexample, consider
$$ g(x) = x\_0 \oplus \left[x\_1 \land \cdots \land x\_{n-\sqrt{n}-1} \land (x\_{n-\sqrt{n}} \oplus
\cdots \oplus x\_{n-1})\right]. $$
This function is almost always equal to $x\_0$, so almost all of its Fourier spectrum is on the first two levels.

> **Comments:**
> **username_6**: Do you have any robust examples where the function can't be approximated in AC0?  
> **username_5**: A function concentrated on the first $O(1)$ levels is always close to a function depending on $O(1)$ inputs, so if we're interested in only $O(1)$ levels, then there are no robust examples.  
> **username_5**: @Arul A Fourier level consists of all Fourier coefficients corresponding to sets of a given size. We think of them as ordered in increasing order of size. As for why this function is hard for AC0, this is an exercise. Hint: parity is hard for AC0.  

---

### Answer by username_4 on 2013-01-02. Score: 7

There are several ways to understand the question according to the precise meaning of "small size" and "concentrate."

1) If you consider Boolean functions so that $1-o(1)$ of their l-2 norm is concentrated on small sized $S$ then the answer is no - the majority function is an example such that $1-o(1)$ of the l-2 norm is on bounded sets and is not in ${\rm AC^0}$.

2) There is a theorem of Bourgain that if the concentration is well above that of the majority function then the function is approximately a Junta, and thus depends on O(1) variables.

3) You can ask that the total influence which is expectation of |S| with respect to the distribution described by $\hat f^2(S)$ is small. For functions in $AC^0$ the total influence is at most ${\rm polylog} (n)$. If the total influence is O(1) then the function is close to a Junta, namely depending on O(1) variables.

4) If the total influence is $O(\log n)$ it is possible but not known that the function is close to a function in $AC^0$.

5) If the total influence is $O(polylog (n))$ then another possibility is a function of bounded depth and $n^{polylog (n)}$ size. It is possible, but unknown, that every function of total influence polylog (n) is close to such a function.


---

