# Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

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 ?

• 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. – Tsuyoshi Ito Sep 20 '12 at 11:37
• 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... – Alessandro Cosentino Sep 20 '12 at 13:29
• 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. – Sasho Nikolov Sep 20 '12 at 14:23
• 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. – Sasho Nikolov Sep 20 '12 at 14:29
• @Strattav Then you could ask that question. – Tyson Williams Sep 20 '12 at 17:00

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.