I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.

I'm new to the subject of "Derandomization," and as such, I wanted to know which reference to start from?

I prefer one that discusses literature and history, as well as the technical details.

  • 3
    Arora and Barak's textbook on computational complexity covers derandomization fairly well. Did you have something else in mind? – Ryan Williams Sep 8 '10 at 18:05
  • Thanks. I'll take a look. I don't have anything else in my mind. Just to read and understand some papers, I need to understand derandomization first. – M.S. Dousti Sep 8 '10 at 18:20
up vote 16 down vote accepted

The notes from Salil Vadhan's class, "Pseudorandomness", are excellent for this purpose. He is writing a textbook based on these. The draft version of the book is available online.

  • nice link. Looking forward to the book when it comes out – Suresh Venkat Sep 8 '10 at 20:48
  • Yes, really appreciated. – M.S. Dousti Sep 9 '10 at 15:54

I really like Pseudorandom Generators: A Primer by Oded Goldreich. I think it's very well written and probably at the level you want. (Not very research oriented, but still has technical details.)

  • 1
    It's been published as a book in 2010. – M.S. Dousti Sep 27 '10 at 9:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.