Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 16 down vote favorite
3

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 ?

share|improve this question
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: 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 4 '12 at 2:42
1  
see also polylogarithmic independence fools AC^0 circuits by braverman – vzn Oct 4 '12 at 2:49
show 2 more comments

2 Answers

up vote 16 down vote accepted

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.

share|improve this answer
2  
Do you have any robust examples where the function can't be approximated in AC0? – MCH Sep 29 '12 at 18:02
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 Sep 29 '12 at 23:00
up vote 5 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.