Bisakah seseorang membuktikan

Hasil 1: Teorema Linial-Mansour-Nisan mengatakan bahwa bobot empat fungsi yang dihitung oleh terkonsentrasi pada subset ukuran kecil dengan probabilitas tinggi. $\mathsf{AC}^0$

Hasil 2: The memiliki bobot lebih dari empat, terkonsentrasi pada efisien derajat . $\mathsf{PARITY}$ $n$

Pertanyaan: Apakah ada cara untuk membuktikan (jika dapat dibuktikan) tidak dapat dihitung oleh sirkuit melalui / menggunakan hasil 1 dan 2? $\mathsf{PARITY}$ $\mathsf{AC}^0$

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

Bukankah ini aplikasi yang jelas dari teorema Linial-Mansour-Nisan? Bagaimana teorema LMN dibuktikan (khususnya, apakah itu dibuktikan oleh argumen probabilistik atau tidak) tidak relevan.

Tsuyoshi Ito

pada saat yang sama, bukankah teorema Linial-Mansour-Nisan dibuktikan dengan mengasumsikan teorema Hastad? Bagiku seperti seekor anjing yang mengejar ekornya sendiri ...

Alessandro Cosentino

Ini adalah bagaimana batas bawah pada ukuran sirkuit AC0 yang mendekati paritas diturunkan dalam catatan Ryan O'Donnell . Lihat akibat wajar 32.

Sasho Nikolov

Saya pikir pertanyaan yang lebih menarik adalah dalam komentar Anda: adalah setiap fungsi yang spektrum empatiernya terkonsentrasi pada koefisien tingkat rendah yang dapat dihitung oleh sirkuit AC0 berukuran kecil.

Sasho Nikolov

@ Strattav Kemudian Anda bisa mengajukan pertanyaan itu.

Tyson Williams

Jawaban:

Teorema LMN menunjukkan bahwa jika f adalah fungsi boolean dapat dihitung oleh sirkuit ukuran M, $(f:\{-1,1\}^n \rightarrow \{-1,1\})$ $\text{AC}^0$

\sum_{S : | S | > k} \hat{f} (S)^{2} \leq 2^{- Ω (k / (catatan 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})}$

tidak lain adalah korelasi f dengan fungsi paritas . Biarkan menjadi fraksi input mana berbeda dari . $|\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}$

Jadi, jika M adalah , untuk sama dengan , $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}$

Jadi, teorema LMN tidak hanya membuktikan bahwa tidak dapat dihitung oleh sirkuit , tetapi juga menunjukkan bahwa memiliki korelasi yang rendah dengan sirkuit . $PARITY$ $AC^{0}$ $PARITY$ $AC^{0}$

Tulasi
sumber