Czy można udowodnić za pomocą twierdzenia Linial-Mansour-Nisan i znajomości czteroczęściowego spektrum ?

Wynik 1: Twierdzenie Linial-Mansour-Nisan mówi, że czteroliniowa waga funkcji obliczonych przez obwody jest skoncentrowana na podzbiorach małych rozmiarów z dużym prawdopodobieństwem. $\mathsf{AC}^0$

Wynik 2: ma czterokierunkową wagę skoncentrowaną na współczynniku stopnia . $\mathsf{PARITY}$ $n$

Pytanie: Czy istnieje sposób, aby udowodnić (jeśli można udowodnić), że nie jest obliczalny przez obwody przez / przy użyciu wyników 1 i 2? $\mathsf{PARITY}$ $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
źródło

Czy nie jest to oczywiste zastosowanie twierdzenia Linial-Mansour-Nisan? Sposób udowodnienia twierdzenia LMN (w szczególności, czy dowodzi go argument probabilistyczny, czy nie) jest nieistotny.

Tsuyoshi Ito,

jednocześnie, czy nie dowodzi się twierdzenia Liniala-Mansoura-Nisana przy założeniu twierdzenia Hastada? Wygląda mi jak pies goniący własny ogon ...

Alessandro Cosentino,

W ten sposób dolną granicę wielkości obwodu AC0 zbliżonego do parytetu uzyskuje się w notatkach Ryana O'Donnella . Patrz wniosek 32.

Sasho Nikolov

myślę, że bardziej interesujące pytanie znajduje się w twoim komentarzu: czy każda funkcja, której widmo czterokierunkowe koncentruje się na współczynnikach niskiego poziomu obliczalnych przez małe obwody AC0.

Sasho Nikolov,

@Strattav Następnie możesz zadać to pytanie.

Tyson Williams,

Odpowiedzi:

Twierdzenie LMN pokazuje, że jeśli f jest funkcją logiczną obliczalną przez obwód wielkości 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})}$

jest niczym innym jak korelacją f z funkcją parzystości . Niech być ułamkiem wejściowych, gdzie różni się od . $|\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}$

Tak więc, jeśli M oznacza , na jest równa , $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}$

Twierdzenie LMN nie tylko dowodzi, że nie może być obliczone przez obwody , ale pokazuje również, że ma niską korelację z obwodami . $PARITY$ $AC^{0}$ $PARITY$ $AC^{0}$

Tulasi
źródło