¿Se puede probar

Resultado 1: el teorema de Linial-Mansour-Nisan dice que el peso de Fourier de las funciones calculadas por los circuitos $\mathsf{AC}^0$ se concentra en los subconjuntos de pequeño tamaño con alta probabilidad.

Resultado 2: El $\mathsf{PARITY}$ tiene su peso de Fourier concentrado en el coeficiente de grado $n$ .

Pregunta: ¿Hay alguna manera de demostrar (si es demostrable) que $\mathsf{PARITY}$ no es computable por los circuitos $\mathsf{AC}^0$ través de / usando los resultados 1 y 2?

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
fuente

¿No es esta una aplicación obvia del teorema de Linial-Mansour-Nisan? La forma en que se prueba el teorema de LMN (en particular, si se prueba por argumento probabilístico o no) es irrelevante.

Tsuyoshi Ito

al mismo tiempo, ¿no se prueba el teorema de Linial-Mansour-Nisan asumiendo el teorema de Hastad? Me parece un perro persiguiendo su propia cola ...

Alessandro Cosentino

Así es como el límite inferior en el tamaño de un circuito AC0 que se aproxima a la paridad se deriva en las notas de Ryan O'Donnell . Ver corolario 32.

Sasho Nikolov

Creo que la pregunta más interesante está en su comentario: es cada función cuyo espectro de Fourier se concentra en coeficientes de bajo nivel computables por circuitos AC0 de pequeño tamaño.

Sasho Nikolov

@Strattav Entonces podrías hacer esa pregunta.

Tyson Williams

Respuestas:

El teorema de LMN muestra que si f es una función booleana computable por un circuito de tamaño 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})}$

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