Foundations and Trends® in Theoretical Computer Science > Vol 7 > Issue 1–3

Pseudorandomness

By Salil P. Vadhan, School of Engineering and Applied Sciences, Harvard University, USA, salil@seas.harvard.edu

 
Suggested Citation
Salil P. Vadhan (2012), "Pseudorandomness", Foundations and Trends® in Theoretical Computer Science: Vol. 7: No. 1–3, pp 1-336. http://dx.doi.org/10.1561/0400000010

Publication Date: 20 Dec 2012
© 2012 S. P. Vadhan
 
Subjects
Randomness in computation,  Computational aspects of combinatorics and graph theory,  Computational aspects of communication,  Computational complexity,  Computational models and complexity,  Cryptography and information security,  Design and analysis of algorithms,  Computational algebra,  Coding theory and practice,  Information theory and computer science
 
Keywords
Randomness in computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 The Power of Randomness 
3 Basic Derandomization Techniques 
4 Expander Graphs 
5 List-Decodable Codes 
6 Randomness Extractors 
7 Pseudorandom Generators 
8 Conclusions 
Acknowledgments 
References 

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

DOI:10.1561/0400000010
ISBN: 978-1-60198-594-1
350 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-595-8
350 pp. $330.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: The Power of Randomness
3: Basic Derandomization Techniques
4: Expander Graphs
5: List-Decodable Codes
6: Randomness Extractors
7: Pseudorandom Generators
8: Conclusions
References

Pseudorandomness

Pseudorandomness is the theory of efficiently generating objects that "look random" despite being constructed using little or no randomness. This book 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 book also illustrates the significance that the theory of pseudorandomness has for the study of computational complexity, algorithms, cryptography, combinatorics, and communications. The presentation assumes a good undergraduate background in the theory of computation, and general mathematical maturity. Specifically, it is assumed that the reader is familiar with basic algorithms and discrete mathematics. The structure of the monograph makes it ideal for teaching a graduate-level course, with exercises accompanying each chapter.

 
TCS-010