Pseudorandomness
[draft survey/monograph]

 

Salil Vadhan


Abstract

Pseudorandomness is the theory of efficiently generating objects that ``look random'' despite being constructed using little or no randomness. This survey of the subject places particular emphasis on the intimate connections that have been discovered between a variety of fundamental ``pseudorandom objects'' that at first seem very different in nature: expander graphs, randomness extractors, list-decodable error-correcting codes, samplers, and pseudorandom generators. The survey also illustrates the significance the theory of pseudorandomness has for the study of computational complexity, algorithms, cryptography, combinatorics, and communications. The structure of the presentation is meant to be suitable for teaching in a graduate-level course, with exercises accompanying each chapter.


Draft version in preparation for Foundations and Trends in Theoretical Computer Science (now publishers)

Comments Welcome!

  • Full text as of April 2011 (186 pages) [pdf]
  • Frontmatter [pdf]
  • Chapter 1: Introduction [pdf]
  • Chapter 2: The Power of Randomness [pdf]
  • Chapter 3: Basic Derandomization Techniques [pdf]
  • Chapter 4: Expander Graphs [pdf]
  • Chapter 5: List-Decodable Codes [pdf]
  • Chapter 6: Randomness Extractors (missing references) [pdf]
  • Chapter 7: Pseudorandom Generators (missing references & exercises) [pdf]
  • Chapter 8: Conclusions (to be written, but see my survey The Unified Theory of Pseudorandomness)
  • References [pdf][bib]
  • August 2010 version [pdf]

See also



 [ back to Salil Vadhan's research]