Borel-Cantelli Lemma und Derandomisierung

11

Ich las einen Artikel mit dem Titel Random Oracles with (out) Programmability . Der letzte Absatz von Abschnitt 2.3 lautet:

[Mit unserem neuartigen Ansatz] Es ist nicht erforderlich, bekannte klassische asymptotische (und einheitliche) Derandomisierungstechniken anzuwenden, die auf dem Borel-Cantelli-Lemma basieren . Nach unserem besten Wissen ist dieser Ansatz in diesem Artikel neu.

Ich habe mir den Wikipedia-Eintrag für Borel-Cantelli-Lemma angesehen und die Idee fast verstanden. Ich konnte jedoch immer noch nicht herausfinden, wie es mit der Derandomisierung zusammenhängt. Außerdem verstehe ich die Bedeutung von "asymptotisch" und "einheitlich" im oben genannten Absatz nicht.

PS: Das Googeln nach Borel-Cantelli und die Derandomisierung werden einige interessante Ergebnisse zeigen, aber ich habe nicht genug Hintergrund, um sie gut zu verstehen.

cc.complexity-theory derandomization pr.probability measure-theory MS Dousti
quelle
2
Winziges Kommentar: Die Verwendung des Borel-Cantelli-Lemmas in der Komplexitätstheorie scheint mit der von Lutz eingeführten ressourcengebundenen Maßtheorie und einigen Folgemaßnahmen hier , hier und hier in Zusammenhang zu stehen . Diese Frage interessiert mich auch, ich hoffe, wir haben ein paar nette Antworten!
Hsien-Chih Chang 8 之
@ Hsien-Chih: Danke. Ich habe auch Lutz 'Werke gesehen, aber sie waren mir zu kompliziert :( Ich hoffe, jemand beschreibt sie in "
Laienbegriffen
t

Antworten:

3

Ich denke nicht, dass sie Derandomisierung im traditionellen Sinne bedeuten. Schauen Sie sich die Anwendung des BC-Lemmas in diesem Artikel an, um ein Beispiel dafür zu finden, worüber sie sprechen: http://www.cs.bu.edu/~reyzin/hash.html .

Sie sagen "asymptotisch", weil die meisten BB-Trennungen für Konzepte wie Einwegfunktionen gelten, die asymptotisch definiert sind. Ihr Ergebnis ist stattdessen eine "konkrete" Grenze, die für alle Werte der Sicherheitsparameter gilt, nicht nur für ausreichend große Werte.

David Cash
quelle