Beigel-Tarui-Transformation von ACC-Cricuits

Ich lese den Anhang über ACC-Untergrenzen für NEXP in Aroras und Baraks Computational Complexity- Buch. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Eines der Schlüsselmotive ist eine Transformation von -Kreisen zu mehrlinearen Polynomen über die ganzen Zahlen mit polylogarithmischem Grad und Quasipolynomkoeffizienten oder äquivalent dazu die Schaltungsklasse , die die Klasse der zwei tiefen Schaltungen mit quasipolynomiell vielen UND-Gattern auf der unteren Ebene mit polylogarithmischem Fan-In und einem symmetrischen Gate auf der oberen Ebene ist. S Y M $ACC^{0}$$SYM^{+}$

Im Anhang zum Lehrbuch besteht diese Transformation aus drei Schritten, wobei angenommen wird, dass die Gate-Menge aus OR, mod , mod und der Konstante . Der erste Schritt besteht darin, das Fan-In der OP-Gatter auf polylogarithmische Ordnung zu reduzieren.3 $2$$3$$1$

Mit dem Valiant-Vazirani-Isolations-Lemma erhalten die Autoren, dass ein ODER-Gatter über Eingaben der Form ist, wenn wir Wählen Sie , um eine paarweise unabhängige Hash-Funktion von bis , und dann für ein beliebiges . mit einer Wahrscheinlichkeit von mindestens es halten, dass . O R ( x 1 , . . . , X 2 k ) h [ 2 k ] { 0 , 1 } x ∈ { 0 , 1 } 2 k 1 / ( 10 k ) Σ i : h ( i ) = 1 x i mod $2^{k}$$OR (x_{1},...,x_{2^{k}})$$h$$[2^{k}]$$\{ 0,1 \}$$x \in \{0,1\}^{2^{k}}$$1/(10k)$$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$

Ist die Wahrscheinlichkeit von mindestens ? Es scheint, dass eine schwache Untergrenze ist.1 / 2 1 / 10 $\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2$$1/2$$1/10k$

Der zweite Schritt ist das Bewegen zu arithmetischen Gattern und das Herunterdrücken von Multiplikationen. In diesem Schritt transformieren wir Boolesche Schaltungen mit einer gegebenen Binäreingangszeichenfolge in eine Arithmetikschaltung mit einer Ganzzahleingabe.

Hier stellen sie fest, dass durch und wird durch wobei Fermats kleiner Satz verwendet wird.$OR(x_{1},...,x_{k})$$1-x_{1}x_{2}\cdots x_{k}$$MOD_{p}(x_{1},...,x_{k})$$(\Sigma_{i=1,...,k} x_{i})^{p-1}$

Warum ergibt dieser Ersatz eine äquivalente Schaltung?$SYM^{+}$

Ist nicht die Wahrscheinlichkeit von mindestens 1/2? Es scheint, dass 1 / ( 10 k ) eine schwache Untergrenze ist.$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$1/(10k)$

Tatsächlich lautet die Antwort nein. (Es wäre , dass gilt mit einer Wahrscheinlichkeit von mindestens 1 / 2 - ε , wenn wir mit einer arbeiteten ε -biased Hash - Familie, und zwar unter Verwendung von ε -biased Hash Funktionen stellen eine Möglichkeit zur Verbesserung der Konstruktionsparameter dar. Die paarweise Unabhängigkeit ist jedoch nicht unbedingt ε- voreingenommen.)$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$1/2-\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$

Es scheint, dass ihnen hier ein zusätzlicher Schritt fehlt. Um Valiant-Vazirani direkt anzuwenden, müssten Sie auch den Bereich der Hash-Funktion zufällig auswählen. Anstatt zufällige paarweise unabhängige auszuwählen, sollten Sie anscheinend zufällige ℓ ∈ { 2 , … , k + 1 } auswählen und dann zufällige paarweise unabhängige h : [ 2 k ] auswählen. → { 0 , 1 } $h : [2^k]\rightarrow\{0,1\}$$\ell \in \{2,\ldots,k+1\}$$h : [2^k]\rightarrow \{0,1\}^{\ell}$. (Hier bin ich bewusst mit Arora-Baraks Aussage von Valiant-Vazirani, gefunden auf Seite 354.) Let die Zahl der sein x i = 1 . Valiant-Vazirani sagt , dass , wenn Sie gewählt haben l , so dass 2 l - 2 ≤ s ≤ 2 l - 1 , dann ist die Wahrscheinlichkeit , dass Σ i : h ( i ) = 1 x i = 1 (! Über die ganzen Zahlen) mindestens 1 / 8 .$s$$x_i=1$$\ell$$2^{\ell-2} \leq s \leq 2^{\ell-1}$$\Sigma_{i:h (i) =1} x_{i} = 1$$1/8$

So durch zufällige Kommissionierung und zufällige paarweise unabhängig Kommissionierung h : [ 2 k ] → { 0 , 1 } l , dann haben Sie wahrscheinlich mindestens 1 / ( 8 k ) , dass Σ i : h ( i ) = 1 x i mod  2 = 1 . Um die zufällige Wahl von ℓ in der Schaltung zu simulieren , können Sie einfach das O R über alle möglichen $\ell$$h: [2^k]\rightarrow\{0,1\}^{\ell}$$1/(8k)$$\Sigma_{i:h (i) =1} x_{i} \mbox{mod } 2 = 1$$\ell$$OR$$\ell$(ihre Anzahl ist in logarithmische , nachdem alle), so dass die Wahrscheinlichkeit des Erfolgs wird mindestens 1 / 8 wieder. Anstatt also O ( k log s ) -Hash-Funktionen mit dem Bereich { 0 , 1 } zu haben , möchten Sie O ( k ) verschiedene Mengen von Hash-Funktionen (jede Menge hat einen anderen Bereich) mit O ( log s ) -Hash-Funktionen in jedem Satz.$2^k$$1/8$$O(k\log s)$$\{0,1\}$$O(k)$$O(\log s)$

Warum ergibt dieser Ersatz eine äquivalente SYM + -Schaltung?

Ein SYM einer UND-Schaltung (dh SYM +) der Größe ist im Wesentlichen äquivalent zu einem multivariaten Polynom h : { 0 , 1 } n → { 0 , … , K } mit höchstens K Monomen, einer Nachschlagetabelle g : { 0 , … , K } → { 0 , 1 } und Berechnen von g ( h ( x 1 , … , x n$K$$h : \{0,1\}^n \rightarrow \{0,\ldots,K\}$$K$$g : \{0,\ldots,K\}\rightarrow \{0,1\}$ . (Ein Beweis kann zum Beispiel in Beigel-Tarui gefunden werden.) Die Intuition ist, dass jedes Monom in f ein UND-Gatter ist und g das SYM-Gatter ist. Ich sage "im Wesentlichen äquivalent", weil das mehrlineare Polynom h für einige Terme auch negative Koeffizienten haben könnte und negative Koeffizienten in SYM von AND offensichtlich nicht implementierbar sind. Aber ich behaupte (und Beigel und Tarui behaupten), dass dies kein Problem ist. Denk darüber nach :)$g(h(x_1,\ldots,x_n))$$f$$g$$h$