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 ?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ This question sounds interesting, though I lack some of the background in fourier analysis. I would appreciate references to related literature. $\endgroup$– MarkusCommented Sep 28, 2012 at 12:49
-
5$\begingroup$ @Markus: this book 2.0 by Ryan O'Donnell is an excellent reference: contrib.andrew.cmu.edu/~ryanod $\endgroup$– Alessandro CosentinoCommented Sep 28, 2012 at 14:06
-
$\begingroup$ 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.... $\endgroup$– vznCommented Sep 28, 2012 at 22:42
-
$\begingroup$ 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...? $\endgroup$– vznCommented Oct 4, 2012 at 2:42
-
1$\begingroup$ see also polylogarithmic independence fools AC^0 circuits by braverman $\endgroup$– vznCommented Oct 4, 2012 at 2:49
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
4
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.
answered Sep 29, 2012 at 5:09
-
3$\begingroup$ Do you have any robust examples where the function can't be approximated in AC0? $\endgroup$ Commented Sep 29, 2012 at 18:02
-
2$\begingroup$ 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. $\endgroup$ Commented Sep 29, 2012 at 23:00
-
$\begingroup$ @YuvalFilmus What does Fourier spectrum level mean? Why is this function hard for $AC^0$? $\endgroup$– user34945Commented Oct 10, 2015 at 9:54
-
$\begingroup$ @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. $\endgroup$ Commented Oct 10, 2015 at 16:20
$\begingroup$
$\endgroup$
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.
