Fourierkoeffizienten Boolesche Funktionen, die durch Schaltungen mit begrenzter Tiefe mit UND ODER- und XOR-Gattern beschrieben werden

Sei eine Boolesche Funktion und betrachte f als eine Funktion von bis . In dieser Sprache ist die Fourier-Expansion von f einfach die Expansion von f in Form von quadratfreien Monomen. (Diese Monome bilden eine Basis für den Raum der reellen Funktionen auf . Die Summe der Quadrate der Koeffizienten ist einfach also führt zu einer Wahrscheinlichkeitsverteilung bei quadratfreien Monomen. Nennen wir diese Verteilung die F-Verteilung.$f$$\{-1,1\}^n$$\{ -1,1 \}$$2^n$$\{-1,1\}^n$$1$$f$

Wenn f durch einen begrenzten Tiefenkreis polynomialer Größe beschrieben werden kann, dann wissen wir durch einen Satz von Linial, Mansour und Nisan, dass sich die F-Verteilung auf Monome mit einer Größe von bis zu einem nahezu exponentiell kleinen Gewicht konzentriert. Dies leitet sich aus dem Hastad-Switching-Lemma ab. (Ein direkter Beweis wäre am wünschenswertesten.)$\text{polylog } n$

Was passiert, wenn wir Mod 2 Gates hinzufügen? Ein zu betrachtendes Beispiel ist die Funktion für Variablen, die als das innere Produkt von Mod 2 der ersten n Variablen und der letzten n Variablen beschrieben wird. Hier ist die F-Verteilung gleichmäßig.$IP_{2n}$$2n$

Frage : Ist die F-Verteilung einer Booleschen Funktion, die durch die Polynomgröße mit begrenzter Tiefe UND, ODER, Schaltung beschrieben wird, auf "Ebenen" konzentriert (bis zu einem superpolynomiell kleinen Fehler) ?$_2$$o(n)$

Bemerkungen :

1. Ein möglicher Weg zu einem Gegenbeispiel wäre, verschiedene auf nicht zusammenhängende Sätze von Variablen zu "kleben" , aber ich verstehe nicht, wie das geht. Vielleicht sollte man die Frage abschwächen und es erlauben, den Variablen eine Gewichtung zuzuweisen, aber ich sehe auch keinen klaren Weg, dies zu tun. (Es gehört also auch dazu, dass ich mich auf diese beiden Dinge beziehe.)$_2k$

2. Ich würde spekulieren, dass eine positive Antwort auf die Frage (oder auf eine erfolgreiche Variante) auch dann zutrifft, wenn Sie mod Gatter zulassen . (Die Frage wurde also von Ryan Williams 'jüngstem beeindruckendem ACC-Ergebnis motiviert.) $_k$

3. Für MAJORITY ist die F-Verteilung für jede "Ebene" groß (1 / poly).

Wie von Luca gezeigt, lautet die Antwort auf die von mir gestellte Frage "nein". Es bleibt die Frage, wie Eigenschaften der F-Verteilungen von Booleschen Funktionen gefunden werden können, die durch UND-ODER- und Mod-2-Gatter beschrieben werden können, die von MAJORITY nicht gemeinsam genutzt werden.

Ein Versuch, die Frage zu speichern, indem über MONOTONE-Funktionen gesprochen wird:

Frage : Ist die F-Verteilung einer MONOTONE-Booleschen Funktion durch eine begrenzte Tiefenpolynomgröße UND / ODER / Schaltung beschrieben, die auf "Ebenen" konzentriert ist (bis zu einem superpolynomiell kleinen Fehler) ?$_2$$o(n)$

Wir können spekulieren, dass wir durch ersetzen können, so dass ein Gegenbeispiel für diese starke Version interessant sein kann. $o(n)$$\text{polylog} (n)$

Gil, wäre so etwas ein Gegenbeispiel?

Sei so, dass , und stelle dir eine Bit-Eingabe als ein Paar wobei eine m-Bit-Zeichenfolge und eine ganze Zahl ist im Bereich binär geschrieben.$m$$n=m+\log m$$n$$(x,i)$$x$$(x_1,\ldots ,x_m)$$i$$1,\ldots,m$

Dann definieren wir$f(x,i):= x_1 \oplus \cdots \oplus x_i$

Für jedes die Funktion f () eine Korrelation mit dem Fourier-Zeichen , und daher hat die "Ebene i" mindestens Bruchteil der Masse. (In der Tat mehr, aber das sollte ausreichen)$i=1,\ldots,m$$1/m$$x_1 \oplus \cdots \oplus x_i$$1/m^2$

f () kann in Tiefe 3 realisiert werden: Setzen Sie alle XORs in eine Ebene und führen Sie dann die "Auswahl" in zwei Ebenen von ANDs, ORs und NOTs durch (wobei die NOTs nicht wie üblich zur Tiefe addiert werden).