Anfängerleitfaden zur Derandomisierung

17

Ich habe das Buch Pairwise Independence and Derandomization zu diesem Thema gefunden, aber es ist eher forschungsorientiert als tutorialorientiert.

Ich bin neu im Thema "Derandomisierung", und als solches wollte ich wissen, von welchem ​​Verweis ich ausgehen soll?

Ich bevorzuge eine, die sich mit Literatur und Geschichte sowie den technischen Details befasst.

cc.complexity-theory derandomization randomized-algorithms MS Dousti
quelle
3
Aroras und Baraks Lehrbuch zur Komplexität von Berechnungen deckt die Derandomisierung ziemlich gut ab. Hattest du noch etwas anderes im Sinn?
Ryan Williams
Vielen Dank. Ich werde einen Blick darauf werfen. Ich habe nichts anderes im Kopf. Nur um einige Artikel zu lesen und zu verstehen, muss ich zuerst die Derandomisierung verstehen.
MS Dousti

Antworten:

16

Die Noten aus Salil Vadhans Klasse "Pseudozufälligkeit" eignen sich hervorragend für diesen Zweck. Darauf aufbauend schreibt er ein Lehrbuch. Die Entwurfsversion des Buches ist online verfügbar .

Arnab
quelle
netter link. Wir freuen uns auf das Buch, wenn es herauskommt
Suresh Venkat
Ja, sehr geschätzt.
MS Dousti
8

Ich mag Pseudozufallsgeneratoren: Ein Primer von Oded Goldreich. Ich denke, es ist sehr gut geschrieben und wahrscheinlich auf dem Niveau, das Sie wollen. (Nicht sehr forschungsorientiert, hat aber immer noch technische Details.)

Robin Kothari
quelle
1
Es wurde als Buch im Jahr 2010 veröffentlicht.
MS Dousti