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

29

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}2n{1,1}n1f

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.)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.IP2n2n

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) ?2o(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) ?2o(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)polylog(n)

Gil Kalai
quelle
Es scheint eine sehr starke Vermutung zu sein, wäre sehr interessant, wenn es Beweise dafür gibt, dass es wahr sein könnte. Ist die Intuition dahinter, dass Sie für Schaltkreise mit konstanter Tiefe mit Mod-Gates entweder Funktionen haben können, die sehr rauschunempfindlich sind wie Polynome mit niedrigem Grad oder vollkommen zufällig wie die Parität, aber es ist schwierig, etwas in der Mitte wie die Mehrheit zu erzeugen?
Boaz Barak,
Lieber Boaz, (Ich würde ein Gegenbeispiel zu der stark vorgeschlagenen Aussage erwarten.) Re: Intuition, ersetze "vollkommen zufällig" durch "Bernouli-like". Wie ich mich erinnere, ist die F-Verteilung, wenn man ein einzelnes mod k-Gatter betrachtet, wie eine bestimmte Bernouli-Verteilung (dh das Gewicht für | S | ist wie p ^ | S | (1-p) ^ {n- | S |) } für einige p, nicht notwendigerweise p = 1/2. Es sieht also so aus, als würden kleine, begrenzte Tiefenschaltungen mit mod k - Gates in ihren F - Verteilungen solche Bernouli - Verteilungen manipulieren, also vielleicht die Eigenschaft "der meisten Gewichte auf wenigen Ebenen" (oder eine andere) Eigentum von Bernouli-Distributionen) wird aufrechterhalten
Gil Kalai

Antworten:

31

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.mn=m+logmn(x,i)x(x1,,xm)i1,,m

Dann definieren wirf(x,i):=x1xi

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,,m1/mx1xi1/m2

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).

Luca Trevisan
quelle
Ja, Luca, es sieht so aus, als hättest du recht.
Gil Kalai