Vom Extraktor zum Pseudozufallsgenerator?

Luca Trevisan hat gezeigt, wie viele Konstruktionen von Pseudozufallsgeneratoren tatsächlich als Extraktorkonstruktionen betrachtet werden können:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Gibt es eine sinnvolle Unterhaltung? Kann man sich "natürliche" Konstruktionen von Extraktoren als Pseudozufallsgeneratoren (PRG) vorstellen?

Extraktorkonstruktionen scheinen Verteilungen über PRGs zu entsprechen (so dass es keinem Distinguisher gelingt, fast alle von ihnen zu unterscheiden). Gibt es dafür bekannte Anwendungen?

Dies ist eine schöne Forschungsfrage mit mehreren Facetten, und es gibt verschiedene Möglichkeiten, die Frage zu formalisieren, je nachdem, ob Sie mit Extraktor einen Samenextraktor oder einen kernlosen Extraktor meinen und ob Sie mit PRG einen PRG für Boolesche Schaltkreise oder eine spezialisiertere Familie meinen (z. B. epsilon-voreingenommene Räume). Hier sind ein paar informelle Gedanken aus meinem Kopf (aber keine vollständige Antwort):

• Bei Saatgutextraktoren gegen Black-Box-PRGs (wie bei Nisan-Wigderson) scheint Black-Box-PRG ein stärkeres Objekt zu sein als bei Extraktoren. Wenn Sie sich den Extraktor von Trevisan ansehen, handelt es sich nicht nur um einen durch Polynome berechenbaren Extraktor, sondern es gibt auch eine wichtige zusätzliche Eigenschaft. Die Analyse enthält nämlich ein lokales und effizientes Rechenelement (nämlich einen lokalen Listendecodierungsalgorithmus). Diese zusätzliche Funktion ist für einen Extraktor nicht so wichtig (als kombinatorisches Objekt, auch wenn der Extraktor polynomiell berechenbar sein muss), aber für einen PRG von entscheidender Bedeutung (damit ein Distinguisher effizient in einen Algorithmus zur Berechnung des PRG umgewandelt werden kann) harte Funktion). Tatsächlich kann dies formalisiert werden, und Ta-Shma und Zuckerman haben bereits die Definition eines "Black-Box-PRG" in ihrem Artikel "Extractor Codes" formalisiert. Sie zeigen, dass Black-Box-PRGs zum Bau von Extraktoren verwendet werden können. Umgekehrt denke ich, man kann zeigen, dass jeder Extraktor, der die obige Eigenschaft erfüllt, einem Black-Box-PRG entspricht (in der Extraktorsprache würde dies bedeuten, dass der resultierende Extraktorcode einen effizienten Soft-Decision-Listendecoder haben muss). Sie können auch Vadhans Artikel "The Unified Theory of Pseudorandomness" finden, der für diese Diskussion relevant ist.

• In der Welt der kernlosen Extraktoren zeigen Trevisan und Vadhan, dass harte Funktionen für eine bestimmte Schaltkreisfamilie zu Extraktoren für diese Familie führen (Papier "Extractors for Samplable Sources"). So kann zum Beispiel eine Funktion, die für AC0 im Durchschnitt sehr schwer ist, aus Quellen extrahiert werden, die von AC0-Schaltkreisen abgetastet wurden (wenn die Min-Entropie der Quelle ausreichend groß ist). Harte Funktionen beziehen sich natürlich auf PRGs (wie von Nisan-Wigderson beobachtet). Hier haben wir also wieder ein etwas anderes Zusammenspiel zwischen PRGs und kernlosen Extraktoren. Es ist jedoch weniger klar, wie man einen Extraktor für abtastbare Quellen verwenden kann (der möglicherweise einige zusätzliche Eigenschaften erfüllt), um eine PRG zu erhalten (der nächste Aufzählungspunkt gibt eine teilweise Antwort darauf). Diese Richtung ist möglicherweise weniger interessant als die obige Diskussion für Saatgut-Extraktoren, da wir bis zu diesem Datum keine

• Aus kombinatorischer Sicht gibt es eine Ähnlichkeit zwischen PRGs und Extraktoren. Wir können eine PRG als eine Menge von Punkten in { 0 , 1 } n (die Ergebnisse der PRG für alle möglichen Samen) oder äquivalent eine Färbung des n- dimensionalen Hyperwürfels in zwei Farben betrachten. In ähnlicher Weise kann ein Extraktor mit einem Ausgabebit (oder einer beliebigen Booleschen Funktion) als eine Menge von Punkten (für die der Extraktor 0 auswertet ) oder als Färbung (im Allgemeinen wäre die Anzahl der Farben 2 m) angesehen werden wobei m die Ausgabelänge ist). Nun täuscht ein PRG mit Punktmenge S eine Funktion mit Punktmenge$S$$\{0,1\}^n$$n$$0$$2^m$$m$$S$ iff | S ∩ F | / | S | liegt in der Nähe von | F | / 2 n . Außerdemextrahiertein Extraktor mit der Punktmenge F aus einer flachen Quelle, die gleichmäßig auf einer Menge von Punkten S iff | verteilt ist S ∩ F | / | S | zu schließen ist 1 / 2 . Diese Ähnlichkeit zwischen den Definitionen erlaubt es, einige aussagekräftige Schlussfolgerungen zu ziehen. Betrachten Sie beispielsweise einen affinen Extraktor über { 0 , $F$$|S \cap F|/|S|$$|F|/2^n$$F$$S$$|S \cap F|/|S|$$1/2$ , das aus der Min-Entropie n - 1 extrahiertund 1 Bitausgibt. Betrachten Sie nun die Menge S der Zeichenfolgen, dievom Extraktor beispielsweise auf 0 abgebildet wurden,und übersetzen Sie sie wie oben in eine "PRG" (mit der Seed-Länge n - 1 ). Die obige Farbinterpretation zeigt nun, dass die resultierende Funktion in der Tat eine PRG für lineare Funktionen ist; Das heißt, wir erhalten einen Epsilon-vorgespannten Generator von einem Extraktor. Dies ist eine sinnvolle Beziehung, aber wahrscheinlich nicht so nützlich, da die resultierende PRG den Keim nur um ein Bit dehnt. Vielleicht lässt sich ein besseres Ergebnis ableiten, wenn der Extraktor mehr Bits ausgibt, aber ich habe das nicht sorgfältig geprüft.$\{0,1\}^n$$n-1$$1$$S$$0$$n-1$

Salil Vadhan schrieb mir, dass die Antwort auf meine Frage bekannt ist und PRGs Extraktoren entsprechen.

Zitiert ihn:

"Siehe Proposition 21 und die darauf folgende Diskussion in meiner Umfrage http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (Es gibt einen Tippfehler -" Black-Box-Härteverstärker "sollte" schwarz "sein -Box PRG Bau ")

Extraktoren sind vergleichbar mit Black-Box-PRG-Konstruktionen, bei denen es Ihnen nur um die Menge der Ratschläge und nicht um die Laufzeit bei der Reduzierung geht. Nach einer begrenzten Laufzeit zu fragen, bedeutet, nach Extraktoren mit "lokaler Listendecodierung" zu fragen.

Zu dieser Frage gibt es ein schönes Papier von Chris Umans für Dispergierer: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf

Er zeigt, dass Dispergierer, die eine Polynom-Zeit-Rekonstruktionsprozedur haben, aber nicht unbedingt die lokale Dekodiereigenschaft, die Existenz von Schlagsatzgeneratoren implizieren.

Hier ist eine andere Möglichkeit, es anzuzeigen: Extraktoren können als listenwiederherstellbare Codes angesehen werden (was eine stärkere Variante von listendekodierbaren Codes ist), und Black-Box-PRGs können von lokalen listenwiederherstellbaren Codes angesehen werden. Dispergierer können als in der Liste wiederherstellbare Codes für Null-Fehler angesehen werden. Was Chris zeigt, ist, dass ein mit einer Liste wiederherstellbarer Code für den Null-Fehler, der eine Prozedur zur Wiederherstellung von Listen in Polynomzeit aufweist, die Existenz eines mit einer Liste wiederherstellbaren Codes mit einer lokalen Prozedur zur Wiederherstellung von Listen impliziert .