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$ – Tsuyoshi Ito Sep 20 '12 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$ – Alessandro Cosentino Sep 20 '12 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$ – Sasho Nikolov Sep 20 '12 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$ – Sasho Nikolov Sep 20 '12 at 14:29
  • 7
    $\begingroup$ @Strattav Then you could ask that question. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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