Pseudorandomness
[survey/monograph]

 

Salil Vadhan


Abstract

This is a survey of pseudorandomness, the theory of efficiently generating objects that "look random" despite being constructed using little or no randomness. This theory has significance for a number of areas in computer science and mathematics, including computational complexity, algorithms, cryptography, combinatorics, communications, and additive number theory. Our treatment 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 structure of the presentation is meant to be suitable for teaching in a graduate-level course, with exercises accompanying each chapter.


  • Foundations and Trends® in Theoretical Computer Science: Vol. 7: No. 1–3, pp 1-336, now publishers, December 2012. [pdf] [official now version]
  • 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 [pdf]
  • Chapter 7: Pseudorandom Generators [pdf]
  • Chapter 8: Conclusions [pdf]
  • References [pdf][bib]
  • Acknowledgments [pdf]
  • August 2012 version [pdf]
  • April 2011 version [pdf]
  • August 2010 version [pdf]

See also



 [ back to Salil Vadhan's research]