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,

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