Foundations and Trends® in Theoretical Computer Science > Vol 1 > Issue 4

Pairwise Independence and Derandomization

Michael Luby, Digital Fountain, USA, Avi Wigderson, Institute for Advanced Study, USA, avi@ias.edu
 
Suggested Citation
Michael Luby and Avi Wigderson (2006), "Pairwise Independence and Derandomization", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 1: No. 4, pp 237-301. http://dx.doi.org/10.1561/0400000009

Published: 22 Aug 2006
© 2006 M. Luby and A. Wigderson
 
Subjects
Design and analysis of algorithms,  Computational complexity,  Algorithmic game theory
 

Free Preview:

Article Help

Share

Download article
In this article:
1 Pairwise Independence
2 Limited Independence Probability Spaces
3 Pairwise Independence and Complexity Classes
4 Recycling Randomness
5 Pseudo-Random Generators
6 Deterministic Counting
Acknowledgements
References

Abstract

This article gives several applications of the following paradigm, which has proven extremely powerful in algorithm design and computational complexity. First, design a probabilistic algorithm for a given problem. Then, show that the correctness analysis of the algorithm remains valid even when the random strings used by the algorithm do not come from the uniform distribution, but rather from a small sample space, appropriately chosen. In some cases this can be proven directly (giving "unconditional derandomization"), and in others it uses computational assumptions, like the existence of 1-way functions (giving "conditional derandomization").

The article is based on a series of lectures given by the authors in 1995, where the notes were scribed by the attending students. (The detailed list of scribes and other contributors can be found in the Acknowledgements section at the end of the manuscript.) The current version is essentially the same, with a few minor changes. We note that this publication takes place a decade after the lectures were given. Much has happened in the area of pseudorandomness and derandomization since, and perhaps a somewhat different viewpoint, different material, and different style would be chosen were these lectures given today. Still, the material presented is self contained, and is a prime manifestation of the "derandomization" paradigm. The material does lack references to newer work though. We recommend the reader interested in randomness, derandomization and their interplay with computational complexity to consult the following books and surveys, as well as their extensive bibliography: [31, 14, 36, 37, 21, 42].

DOI:10.1561/0400000009
ISBN: 978-1-933019-22-2
88 pp. $100.00
Buy book
 
ISBN: 978-1-933019-76-5
88 pp. $100.00
Buy E-book
Table of contents:
1. Pairwise Independence
2. Limited Independence Probability Spaces
3. Pairwise Independence and Complexity Classes
4. Recycling randomness
5. Pseudo-random generators
6. Deterministic Counting
Acknowledgements
References

Pairwise Independence and Derandomization

Pairwise Independence and Derandomization gives several applications of the following paradigm, which has proven extremely powerful in algorithm design and computational complexity. First, design a probabilistic algorithm for a given problem. Then, show that the correctness analysis of the algorithm remains valid even when the random strings used by the algorithm do not come from the uniform distribution, but rather from a small sample space, appropriately chosen. In some cases this can be proven directly (giving "unconditional derandomization"), and in others it uses computational assumptions, like the existence of 1-way functions (giving "conditional derandomization"). Pairwise Independence and Derandomization is self contained, and is a prime manifestation of the "derandomization" paradigm. It is intended for scholars and graduate students in the field of theoretical computer science interested in randomness, derandomization and their interplay with computational complexity.

 
TCS-009