Deterministische Fehlerreduzierung, Stand der Technik?

12

Angenommen, man hat einen randomisierten (BPP) Algorithmus A Verwendung von r Zufallsbits . Natürliche Wege , um ihre Erfolgswahrscheinlichkeit zu verstärken 1δ , für jede gewählte δ>0 , sind

  • Unabhängige Läufe + Mehrheitsabstimmung: Laufen Sie A unabhängig T=Θ(log(1/δ) Male und nehmen Sie die Mehrheitsabstimmung der Ausgänge. Dies erfordert rT=Θ(rlog(1/δ)) Bits der Zufälligkeit, und sprengt die Laufzeit um einen T=Θ(log(1/δ)) Faktor.
  • Paarweise unabhängige Läufe + Chebyshev: Führe A "paarweise unabhängig" T=Θ(1/δ) Male aus und vergleiche mit einem Schwellenwert. Dies erfordert rT=Θ(r/δ) Bits der Zufälligkeit und sprengt die Laufzeit um ein T=Θ(1/δ) Faktor.

Karp, Pippenger und Sipser [1] (anscheinend, ich meine Hände nicht auf dem Papier bekommen konnte selbst, es ist ein Second-Hand - Konto) vorgesehen alternative Ansätze basierend auf starken regelmäßigen Expandern: im Wesentlichen finden Sie in den 2r Knoten des Expanders wie die zufälligen Samen. Wählen Sie einen zufälligen Knoten des Expanders mit den r zufälligen Bits und dann

  • Machen Sie von dort aus einen kurzen zufälligen Spaziergang der Länge T=Θ(log(1/δ)) und führen Sie A auf den T Seeds aus, die den Knoten auf dem Pfad entsprechen, bevor Sie eine Mehrheitsentscheidung treffen. Dies erfordert r+T=r+Θ(log(1/δ)) Bits der Zufälligkeit und vergrößert die Laufzeit um einen T=Θ(log(1/δ)) Faktor.

  • Führen Sie A auf allen Nachbarn des aktuellen Knotens (oder allgemeiner auf allen Knoten in einem Abstand c zum aktuellen Knoten) aus, bevor Sie eine Mehrheitsentscheidung treffen. Dies erfordert r Bits der Zufälligkeit und erhöht die Laufzeit um einen T=d Faktor, wobei d der Grad (oder dc für die Entfernung c Nachbarschaft) ist. Wenn die Parameter gut eingestellt werden, kostet dies T=poly(1/δ) hier.

Ich interessiere mich für die letzte Kugel, die einer deterministischen Fehlerreduzierung entspricht. Hat es nach [1] eine Verbesserung gegeben, die die Abhängigkeit von T von δ verringert ? Was ist aktuell am besten erreichbar - 1/δγ für welches γ>1 ? γ>0 ? (Für BPP ? Für RP ?)

Hinweis: Ich interessiere mich auch (sehr) für RP anstelle von BPP . Wie in [2] eingeführt, handelt es sich bei der relevanten Konstruktion dann nicht mehr um Expander, sondern um Dispergierer (siehe z. B. diese Vorlesungsnotizen von Ta-Shma, insb. Tabelle 3). Ich konnte jedoch weder die entsprechenden Grenzen für die deterministische (kein einziges zufälligeres Bit als das zulässige r ) Verstärkung finden, noch (was noch wichtiger ist), welche expliziten Dispergiererkonstruktionen nach dem Stand der Technik für den relevanten Bereich von Parametern vorliegen .


[1] Karp, R., Pippenger, N. und Sipser, M., 1985. Ein Kompromiss zwischen Zeit und Zufälligkeit . In der AMS-Konferenz über probabilistische Computerkomplexität (Band 111).

[2] Cohen, A. und Wigderson, A., 1989, Oktober. Disperser, deterministische Verstärkung und schwache Zufallsquellen. In 30th Annual Symposium on Foundations of Computer Science (S. 14-19). IEEE.

Clement C.
quelle
Ich verstehe Folgendes (hauptsächlich auf den oben erwähnten Vorlesungsnotizen von Ta-Shma , denen von van Melkebeek und denen von Cynthia Dwork . Soweit ich das beurteilen kann, sind Dispergierer großartig, um exponentiell zu verstärken, wenn ein paar weitere zufällige Bits gegeben sind , aber nicht wenn Es gibt 0 zusätzliche Zufälligkeiten.
Clement C.
(Wenn jemand bereit ist, diese wenigen zusätzlichen Bits zu verwenden, dann hat Ta-Shmas Vorlesung einen sehr umfangreichen Satz von zusammenfassenden Tabellen). Ohne zusätzliche Zufälligkeit sieht der expander-basierte BPP / RP-Ansatz wie der einzige aus (siehe van Melkebeeks Notizen für BPP, Dworks für die RP-Variante): Beide sind sehr ähnlich und basieren auf dem Papier [1], von dem ich konnte kein direktes pdf finden). Keine scheint eine explizite gebunden auf dem Grad des Polynoms in dem geben , wie es auf den Grad und die Expansion des Expanders Graphen abhängt. poly(1/δ)
Clement C.
Es wird in mindestens linear sein : aber was wird es für die (derzeit) bekanntesten Konstruktionen von Expandergraphen sein? Eigentlich auch für probabilistische Konstruktionen? 1/δ
Clement C.
Ebenfalls relevant (aber nicht antwortet die spezifische Frage): Abschnitt 3.5.4 und Abschnitt 4 (Aufgabe 4.6) von Salil Vadhan des Pseudozufälligkeit .
Clement C.

Antworten:

3

Gibt van Melkebeeks Vorlesungsskript nicht bereits eine O(1/δ) -Grenze an? Die dortige Schranke ist λ höchstens O(δ)und wir könnenλ=O(1/d)Verwendung bestehender Konstruktionen.

Auch in Dworks Vorlesungsskripten ist die Bedingung, dass die Ausdehnung für eine Konstante C C/δ (bei Betrachtung eines Punktes im Abstand c wird im Wesentlichen die Potenzierung verwendet, um die Ausdehnung zu verbessern). Was wiederum mit Grad O ( 1 / δ ) erreicht werden kann .CO(1/δ)

Ω(1/δ)

Gast
quelle
α>0dR=2rλδCαCαd(N,d)λC/d for all N, d, all we need is d=Oα(1/δ) for the bound to be satisfied.
Clement C.
For instance, arbitrarily large Ramanujan graphs are known to exist (constructively) for any degree d such that d1 is a prime power. But do we have explicit constructions of graphs with λ=O(1/d) for all n (or, let's say, for all n which is a power of two)? (I'm not knowledgeable enough on that, and the only result of that sort I could find is Balu-Linial's construction which gives O((log3d)/d) and is not strongly explicit).
Clement C.