Kann man mit dem Linial-Mansour-Nisan-Theorem und der Kenntnis des Fourier-Spektrums von ?

Ergebnis 1: Das Linial-Mansour-Nisan-Theorem besagt, dass das der von den Schaltkreisen berechneten Funktionen sich mit hoher Wahrscheinlichkeit auf die kleinen Teilmengen konzentriert. $\mathsf{AC}^0$

Ergebnis 2: Das konzentriert sich auf den des Grades . $\mathsf{PARITY}$ $n$

Frage: Gibt es eine Möglichkeit zu beweisen (falls nachweisbar), dass nicht mit Kreisen über / unter Verwendung der Ergebnisse 1 und 2 berechenbar ist ? $\mathsf{PARITY}$ $\mathsf{AC}^0$

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

Ist das nicht eine offensichtliche Anwendung des Satzes von Linial-Mansour-Nisan? Wie der LMN-Satz bewiesen wird (insbesondere, ob er durch probabilistische Argumentation bewiesen wird oder nicht), ist unerheblich.

Tsuyoshi Ito

Wird der Satz von Linial-Mansour-Nisan nicht gleichzeitig durch die Annahme des Satzes von Hastad bewiesen? Es sieht für mich aus wie ein Hund, der seinen eigenen Schwanz jagt ...

Alessandro Cosentino

Auf diese Weise wird die untere Schranke der Größe einer AC0-Schaltung, die sich der Parität annähert, in den Notizen von Ryan O'Donnell abgeleitet . Siehe Folgerung 32.

Sasho Nikolov

Ich denke, die interessantere Frage ist in Ihrem Kommentar: Ist jede Funktion, deren Fourierspektrum sich auf niedrige Koeffizienten konzentriert, die durch kleine AC0-Schaltungen berechnet werden können?

Sasho Nikolov

@ Strattav Dann könnten Sie diese Frage stellen.

Tyson Williams

Antworten:

Der LMN-Satz zeigt, dass, wenn f eine Boolesche Funktion durch eine -Schaltung der Größe M berechenbar ist , $(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})}$

ist nichts anderes als die Korrelation von f mit der Paritätsfunktion . Sei der Anteil der Eingaben, bei denen von abweicht. $|\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}$

Also, wenn M , für ist gleich , $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}$

$PARITY$ $AC^{0}$ $PARITY$ $AC^{0}$

Tulasi
quelle