|
Pairwise Independence and Derandomization
Foundations and Trends® in
Theoretical Computer Science
Volume 1 Issue 4
DOI: 10.1561/0400000009
Pairwise Independence and Derandomization
Michael Luby
Digital Fountain, Fremont, CA, USA
Avi Wigderson
Institute for Advanced Study, Princeton, NJ, USA, avi@ias.edu
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: [1, 2, 3, 4, 5, 6].
|