18

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.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 3
    Arora and Barak's textbook on computational complexity covers derandomization fairly well. Did you have something else in mind? – Ryan Williams Sep 08 '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. – Sadeq Dousti Sep 08 '10 at 18:20

2 Answers2

18

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.

arnab
  • 7,000
  • 1
  • 38
  • 55
9

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.)

Robin Kothari
  • 13,617
  • 2
  • 60
  • 116