Przewodnik dla początkujących dotyczący derandomizacji

17

Znalazłem książkę Pairwise Independence and Derandomization na ten temat, ale jest ona bardziej zorientowana na badania niż na samouczek.

Jestem nowy w temacie „Derandomizacji” i dlatego chciałem wiedzieć, od którego odniesienia zacząć?

Wolę taki, który omawia literaturę i historię, a także szczegóły techniczne.

cc.complexity-theory derandomization randomized-algorithms MS Dousti
źródło
3
Podręcznik Arory i Baraka o złożoności obliczeniowej dość dobrze obejmuje derandomizację. Czy miałeś na myśli coś innego?
Ryan Williams,
Dzięki. Spojrzę na to. Nie mam nic innego na myśli. Aby przeczytać i zrozumieć niektóre artykuły, najpierw muszę zrozumieć derandomizację.
MS Dousti,

Odpowiedzi:

16

Nuty z klasy Salila Vadhana „Pseudorandomness” są doskonałe do tego celu. Na tej podstawie pisze podręcznik. Wersja robocza książki jest dostępna online .

arnab
źródło
fajny link. Czekamy na książkę, gdy się pojawi
Suresh Venkat
Tak, bardzo doceniam.
MS Dousti,
8

Naprawdę lubię Pseudorandom Generators: A Primer autorstwa Oded Goldreich. Myślę, że jest bardzo dobrze napisany i prawdopodobnie na pożądanym poziomie. (Nie bardzo zorientowany na badania, ale wciąż ma szczegóły techniczne.)

Robin Kothari
źródło
1
Został opublikowany jako książka w 2010 roku.
MS Dousti