Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability.

Result 2: The $\mathsf{PARITY}$ has its fourier weight concentrated on the co-efficient of degree $n$.

Question: Is there a way to prove(if provable) $\mathsf{PARITY}$ is not computable by $\mathsf{AC}^0$ circuits via/using the results 1 and 2 ?

  • 7
    $\begingroup$ Isn’t this an obvious application of the Linial-Mansour-Nisan theorem? How the LMN theorem is proved (in particular, whether it is proved by probabilistic argument or not) is irrelevant. $\endgroup$ Sep 20, 2012 at 11:37
  • 3
    $\begingroup$ at the same time, isn't Linial-Mansour-Nisan theorem proved by assuming Hastad theorem? It looks to me like a dog chasing its own tail... $\endgroup$ Sep 20, 2012 at 13:29
  • 3
    $\begingroup$ This is how the lower bound on the size of an AC0 circuit approximating parity is derived in Ryan O'Donnell's notes. See corollary 32. $\endgroup$ Sep 20, 2012 at 14:23
  • 5
    $\begingroup$ i think the more interesting question is in your comment: is every function whose fourier spectrum is concentrated on low-level coefficients computable by small-size AC0 circuits. $\endgroup$ Sep 20, 2012 at 14:29
  • 7
    $\begingroup$ @Strattav Then you could ask that question. $\endgroup$ Sep 20, 2012 at 17:00

1 Answer 1


LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M,

$$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$$

$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$|\hat f([n])|$ is nothing but the correlation of f with the parity function $(\prod_{i = 1}^{n}x_i)$. Let $\delta$ be the fraction of inputs where $f$ differs from $PARITY$.

\begin{align} 1 -2 \delta \leq |1 - 2\delta| &= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\ \Rightarrow \delta &\geq 1 - 2^{-\Omega(n/(\log M)^{d-1})} \end{align}

So, if M is $poly(n)$, for $f$ to be equal to $PARITY$,

\begin{align} \delta &\leq \frac{1}{2^n}\\ \Rightarrow 2^n &\geq 2^{(cn/(\log M)^{d-1})}\\ \Rightarrow (\log M)^{d-1} &\geq (c-1)n \\ \Rightarrow M &\geq 2^{\Omega (n^{1/d-1})} \end{align}

So, LMN theorem not only proves that $PARITY$ cannot be computed by $AC^{0}$ circuits, it also shows that $PARITY$ has low correlation with $AC^{0}$ circuits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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