Guía para principiantes sobre la deslealización

17

Encontré el libro Pairwise Independence and Derandomization sobre el tema, pero está más orientado a la investigación que al tutorial.

Soy nuevo en el tema de "Desrandomización" y, como tal, quería saber de qué referencia comenzar.

Prefiero uno que discuta literatura e historia, así como los detalles técnicos.

cc.complexity-theory derandomization randomized-algorithms MS Dousti
fuente
3
El libro de texto de Arora y Barak sobre la complejidad computacional cubre la desrandomización bastante bien. ¿Tenías algo más en mente?
Ryan Williams
Gracias. Le daré un vistazo. No tengo nada más en mi mente. Solo para leer y comprender algunos documentos, primero necesito entender la desrandomización.
MS Dousti

Respuestas:

16

Las notas de la clase de Salil Vadhan, "Pseudoaleatoriedad" , son excelentes para este propósito. Él está escribiendo un libro de texto basado en estos. La versión borrador del libro está disponible en línea .

arnab
fuente
buen enlace Esperando con ansias el libro cuando salga
Suresh Venkat
Sí, realmente lo aprecio.
MS Dousti
8

Realmente me gustan los generadores pseudoaleatorios: una cartilla de Oded Goldreich. Creo que está muy bien escrito y probablemente en el nivel que deseas. (No está muy orientado a la investigación, pero aún tiene detalles técnicos).

Robin Kothari
fuente
1
Ha sido publicado como libro en 2010.
MS Dousti