Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?
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|&gt; 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| &amp;= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\
\Rightarrow \delta &amp;\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 &amp;\leq \frac{1}{2^n}\\
\Rightarrow 2^n &amp;\geq 2^{(cn/(\log M)^{d-1})}\\
\Rightarrow (\log M)^{d-1} &amp;\geq (c-1)n \\
\Rightarrow M &amp;\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.