<p>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,</p>

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

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

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

<p>$|\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$.</p>

<p>\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}</p>

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

<p>\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}</p>

<p>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. </p>

CC BY-SA 3.0
2015-02-10T05:31:28.100Z
2016-10-06T12:59:20.050Z
2016-10-06T12:59:20.050Z
Tulasi
<p>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.</p>

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

<p>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 ?</p>

CC BY-SA 3.0
2012-09-20T09:20:45.893Z
Result 1 is a probabilistic argument and I am not sure and thus would like to know if the result also implies the reverse holds which is, whether the functions with fourier weights concentrated on the smaller sets imply that it would be computable by  $\mathsf{AC}^0$ circuits and if not they can't be.
Stattrav
CC BY-SA 3.0
2012-09-20T11:37:28.633Z
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
CC BY-SA 3.0
2012-09-20T13:29:39.530Z
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
CC BY-SA 3.0
2012-09-20T14:23:54.960Z
This is how the lower bound on the size of an AC0 circuit approximating parity is derived in [Ryan O'Donnell's notes](http://www.contrib.andrew.cmu.edu/~ryanod/?p=819). See corollary 32.
Sasho Nikolov
CC BY-SA 3.0
2012-09-20T14:29:53.333Z
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
CC BY-SA 3.0
2012-09-20T16:36:24.270Z
@SashoNikolov Yes, that is what I really wanted to know.
Stattrav
CC BY-SA 3.0
2012-09-20T17:00:13.580Z
@Strattav Then you could ask that question.
Tyson Williams
CC BY-SA 3.0
2012-09-28T11:18:22.320Z
@AlessandroCosentino i agree with what you have to say.
Stattrav
<cc.complexity-theory><circuit-complexity><boolean-functions><fourier-analysis>
Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?
Stattrav
# Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

(Asked by: username_0 on 2012-09-20)

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 ?

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, fourier-analysis

> **Comments:**
> **username_0**: Result 1 is a probabilistic argument and I am not sure and thus would like to know if the result also implies the reverse holds which is, whether the functions with fourier weights concentrated on the smaller sets imply that it would be computable by  $\mathsf{AC}^0$ circuits and if not they can't be.  
> **username_1**: 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.  
> **username_2**: 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...  
> **username_3**: This is how the lower bound on the size of an AC0 circuit approximating parity is derived in [Ryan O'Donnell's notes](http://www.contrib.andrew.cmu.edu/~ryanod/?p=819). See corollary 32.  
> **username_3**: 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.  
> **username_0**: @SashoNikolov Yes, that is what I really wanted to know.  
> **username_4**: @Strattav Then you could ask that question.  
> **username_0**: @AlessandroCosentino i agree with what you have to say.  

---

## 1 answers

### Answer by username_5 on 2015-02-10. Score: 12

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.


---

