Pairwise Independence and Derandomization
Authors:
Open Access
- 15 March 2006
- journal article
- Published by Emerald Publishing in Foundations and Trends® in Theoretical Computer Science
- Vol. 1 (4) , 237-301
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].Keywords
This publication has 33 references indexed in Scilit:
- Pseudorandom bits for constant depth circuitsCombinatorica, 1991
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- Dispersers, deterministic amplification, and weak random sources1989
- How to recycle random bits1989
- RSA and Rabin Functions: Certain Parts are as Hard as the WholeSIAM Journal on Computing, 1988
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Monte-Carlo algorithms for the planar multiterminal network reliability problemJournal of Complexity, 1985
- Separating the polynomial-time hierarchy by oracles1985
- New hash functions and their use in authentication and set equalityJournal of Computer and System Sciences, 1981
- Two theorems on random polynomial time1978