Peut-on prouver

Résultat 1: le théorème de Linial-Mansour-Nisan dit que le poids de Fourier des fonctions calculées par les circuits $\mathsf{AC}^0$ est concentré sur les sous-ensembles de petite taille à forte probabilité.

Résultat 2: Le a son poids de Fourier concentré sur le coefficient du degré . $\mathsf{PARITY}$ $n$

Question: Existe-t-il un moyen de prouver (si prouvable) que n'est pas calculable par les circuits via / en utilisant les résultats 1 et 2? $\mathsf{PARITY}$ $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
la source

N'est-ce pas là une application évidente du théorème de Linial-Mansour-Nisan? La façon dont le théorème LMN est prouvé (en particulier, s'il est prouvé par un argument probabiliste ou non) n'a pas d'importance.

Tsuyoshi Ito

en même temps, le théorème de Linial-Mansour-Nisan n'est-il pas prouvé en supposant le théorème de Hastad? Il me ressemble à un chien qui court après sa propre queue ...

Alessandro Cosentino

C'est ainsi que la borne inférieure de la taille d'un circuit AC0 se rapprochant de la parité est dérivée dans les notes de Ryan O'Donnell . Voir corollaire 32.

Sasho Nikolov

Je pense que la question la plus intéressante est dans votre commentaire: chaque fonction dont le spectre de Fourier est concentré sur des coefficients de bas niveau calculables par des circuits AC0 de petite taille.

Sasho Nikolov

@Strattav Ensuite, vous pouvez poser cette question.

Tyson Williams,

Réponses:

Le théorème LMN montre que si f est une fonction booléenne calculable par un circuit de taille M, $(f:\{-1,1\}^n \rightarrow \{-1,1\})$ $\text{AC}^0$

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

$\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})}$

n'est rien d'autre que la corrélation de f avec la fonction de parité . Soit être la fraction d'entrées où diffère de . $|\hat f([n])|$ $(\prod_{i = 1}^{n}x_i)$ $\delta$ $f$ $PARITY$

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

$\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}$

$poly(n)$ $f$ $PARITY$ ,

\begin{aligned} δ & \leq \frac{1}{2^{n}} \\ \Rightarrow 2^{n} & \geq 2^{(c n / (\log M)^{d - 1})} \\ \Rightarrow (\log M)^{d - 1} & \geq (c - 1) n \\ \Rightarrow M & \geq 2^{Ω (n^{1 / d - 1})} \end{aligned}

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

Tulasi
la source