Zufallsfunktionen niedrigen Grades als reales Polynom

21

Gibt es eine (sinnvolle) Möglichkeit, eine gleichmäßig zufällige boolesche Funktion deren Grad als reales Polynom höchstens beträgt ?df:{0,1}n{0,1}d

EDIT: Nisan und Szegedy haben gezeigt, dass eine Funktion des Grades von höchstens Koordinaten abhängt , daher können wir annehmen, dass . Die Probleme, wie ich sehe, sind die folgenden: 1) Auf der einen Seite, wenn wir eine zufällige boolesche Funktion auf Koordinaten auswählen , dann wird ihr Grad nahe an , viel höher als . 2) Wenn wir andererseits jeden Gradkoeffizienten höchstens zufällig auswählen , ist die Funktion nicht boolesch.d 2 d n d 2 d d 2 d d 2 d d ddd2dnd2dd2dd2ddd

Die Frage ist also: Gibt es eine Möglichkeit, eine Boolesche Funktion mit niedrigem Grad abzutasten, die diese beiden Probleme vermeidet?

Igor Shinkar
quelle
3
Soll die tatsächliche Funktion die Beschränkung eines reellen Polynoms vom Grad auf 0-1 Eingänge sein, oder soll wenn für ein reelles Polynom von grad höchstens ? Oder etwas anderes? f ( x ) = 1 p ( x ) > 0 p ddf(x)=1p(x)>0pd
Joshua Grochow
3
@ JoshuaGrochow Ich möchte eine Funktion, deren Fourier-Expansion Grad . Das ist Ihre erste Option. d
Igor Shinkar
1
Was ist dein modell Das Aufschreiben der abgetasteten Funktion dauert Mal, oder wenn Sie die Fourier-Erweiterung ausgeben möchten. Ist eine feste Konstante? n O ( d ) d2nnO(d)d
MCH
3
Ich habe der Frage einige Details hinzugefügt.
Igor Shinkar
1
@MCH Wenn eine Funktion vom Grad (mit Nullgewicht über dem Niveau ) ist, kann sie nicht von mehr als Koordinaten abhängen . Dies ist ein Ergebnis von Nisan und Szegedy. Denken Sie an den Sonderfall von . In diesem Fall wissen wir, dass die Funktion von (höchstens) 1 Koordinate abhängt. d d 2 d d = 1ddd2dd=1
Igor Shinkar

Antworten:

11

Hier ist ein Algorithmus, der die trivialen Versuche schlägt.

Das Folgende ist eine bekannte Tatsache (Übung 1.12 in O'Donnells Buch): Wenn eine Boolesche Funktion mit dem Grad as ist ein Polynom, dann ist jeder Fourier-Koeffizient von , ein ganzzahliges Vielfaches von . Mit Cauchy-Schwarz und Parseval erhält man, dass es höchstens Fourier-Koeffizienten ungleich Null und .f:{1,1}n{1,1}dff ( S ) 2 - d 4 d Σ S | F ( S ) | 2 df^(S)2d4dS|f^(S)|2d

Dies legt eine Stichprobenmethode nahe -

  1. Wählen Sie zufällige nicht negative ganze Zahlen für alle Mengen von höchstens , die sich zu summieren .aSS[n]d4d
  2. Sei .f(x)=SaS2dχS(x)
  3. Stellen Sie sicher, dass ein Boolescher Wert ist. Wenn ja, geben Sie . Ansonsten gehe zurück zu .ff1

Beachten Sie, dass für jedes Grad Polynom genau eine Auswahl von Zufallszahlen in Schritt 1 das Polynom . Die Wahrscheinlichkeit für einen bestimmten Grad erhält Polynom Daher müssen wir diesen Prozess höchstens Mal in Erwartung wiederholen , bevor wir anhalten.dffd

1/((nd)+4d4d)=1/O(n/d)d4d.
O(n/d)d4d

Es bleibt zu zeigen, wie Schritt 3 durchzuführen ist. Man kann . Überprüfen Sie, dass (was von Nisan-Szegedy für jede Boolesche Funktion gelten sollte) und werten Sie dann für alle möglichen Zuordnungen zu den Variablen in . Dies kann in der Zeit . Gur und Tamuz bieten für diese Aufgabe einen viel schnelleren zufälligen Algorithmus an, da dieser Teil jedoch die zeitliche Komplexität nicht dominiert, ist dies ausreichend.A={S:aS0}|A|d2dfA2d2d

Insgesamt ergibt der Algorithmus eine Zufallsstichprobe mit einem Grad Polynom in der Zeit . Unter der Annahme, dass die zeitliche Komplexität .dO(nd)d4dnd2d2O(d24d)

Dies ist kein polynomieller Zeitabtastungsalgorithmus, obwohl er viel schneller ist als das Abtasten einer vollständig zufälligen Funktion (in diesem Fall beträgt die Wahrscheinlichkeit, ein bestimmtes Grad Polynom zu erhalten, ).d1/22n

Avishay Tal
quelle
Nett! Tatsächlich ergibt dies einen Algorithmus, von dem whp (wrt ) die maximal mögliche Anzahl von Koordinaten ausgibt, von denen die Funktion niedrigen Grades abhängen kann. Nehmen Sie einfach , um ausreichend groß zu sein, probieren Sie viele Funktionen aus und zählen Sie für jede Funktion die Anzahl der einflussreichen Koordinaten. Geben Sie das Maximum aus, das Sie sehen. n = 10 d 2 ddn=10d2d
Igor Shinkar