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 ?
Asked
Active
Viewed 1,024 times
19
-
This question sounds interesting, though I lack some of the background in fourier analysis. I would appreciate references to related literature. – Markus Sep 28 '12 at 12:49
-
5@Markus: this book 2.0 by Ryan O'Donnell is an excellent reference: http://www.contrib.andrew.cmu.edu/~ryanod/ – Alessandro Cosentino Sep 28 '12 at 14:06
-
almost the converse to Linial, Mansour, Nissan 1993? aaronsons result, counterexample to generalized Linial-Nissan seems close? but imho theres got to be a way to generalize the 1993 result somehow... maybe in a big way.... – vzn Sep 28 '12 at 22:42
-
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 Oct 04 '12 at 02:42
-
1see also polylogarithmic independence fools AC^0 circuits by braverman – vzn Oct 04 '12 at 02:49
-
@vzn Thanks for the additional resource suggestions. – Stattrav Oct 14 '12 at 10:24
-
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 Oct 14 '12 at 16:26
2 Answers
19
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.
Yuval Filmus
- 14,445
- 1
- 48
- 92
-
3Do you have any robust examples where the function can't be approximated in AC0? – Mahdi Cheraghchi Sep 29 '12 at 18:02
-
2A 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 Sep 29 '12 at 23:00
-
@YuvalFilmus What does Fourier spectrum level mean? Why is this function hard for $AC^0$? – Oct 10 '15 at 09:54
-
@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 Oct 10 '15 at 16:20
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.
Gil Kalai
- 6,033
- 35
- 73