Zufallsfunktionen niedrigen Grades als reales Polynom

Gibt es eine (sinnvolle) Möglichkeit, eine gleichmäßig zufällige boolesche Funktion deren Grad als reales Polynom höchstens beträgt ?$f:\{0,1\}^n \to \{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 $d$$d2^d$$n \leq d2^d$$d2^d$$d2^d$$d$$d$

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

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\to\{-1,1\}$$\le d$$f$f ( S ) 2 - d 4 d Σ S | F ( S ) | ≤ 2 d$\hat{f}(S)$$2^{-d}$$4^d$$\sum_{S}{|\hat{f}(S)|}\le 2^{d}$

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 .$a_S$$S\subseteq[n]$$d$$\le 4^d$
2. Sei .$f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$
3. Stellen Sie sicher, dass ein Boolescher Wert ist. Wenn ja, geben Sie . Ansonsten gehe zurück zu .$f$$f$$1$

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.$\le d$$f$$f$$\le d$

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 = \bigcup\{S:a_S\neq 0\}$$|A| \le d 2^d$$f$$A$$2^{d 2^d}$

Insgesamt ergibt der Algorithmus eine Zufallsstichprobe mit einem Grad Polynom in der Zeit . Unter der Annahme, dass die zeitliche Komplexität .$\le d$$O(\frac{n}{d})^{d4^d}$$n \le d2^d$$2^{O(d^2 4^d)}$

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, ).$\le d$$1/2^{2^n}$