Pairwise Independence and Derandomization
Michael Luby and Avi Wigderson
July 1995
This set of notes gives several applications of the
following paradigm. The paradigm consists of two
complementary parts. The first part is to design a
probabilistic algorithm described by a sequence of random
variables so that the analysis is valid assuming limited
independence between the random variables. The second part
is the design of a small probability space for the random
variables such that they are somewhat independent of each other.
Thus, the analysis of the algorithm holds even when the
random variables used by the algorithm are generated
according to the small space.
Click here
to get the postscript file (406K) for this survey.
Approximately 60 pages.
Reference as one of the following:

ICSI TR95035

UC Berkeley UCB/CSD95880

Ecole Normale Superieure LIENS9522
Table of Contents

Lecture 1: Pairwise Independence

Lecture 2: Constructing Hash Functions

Lecture 3: Derandomization Applications

Lecture 4: Hashing

Lecture 5: RP and BPP

Lecture 6: Complexity of Unique Solutions

Lecture 7: BPP is a subset of Sigma_{2}

Lecture 8: AM = IP

Lecture 9: Deterministic Amplification

Lecture 10: ChorGoldreich Generator

Lecture 11: Nisan's Generator

Lecture 12: ImpagliazzoZuckerman Generator

Lecture 13: The Expander Mixing Lemma

Lecture 14: KarpPippengerSipser Generator

Lecture 15: AjtaiKomlosSzemeredi Generator

Lecture 16: Limited Independence Probability Spaces

Lecture 17: OneWay Functions

Lecture 18: Hidden Bit Theorem

Lecture 19: PseudoRandom Generators

Lecture 20: #P and Approximate Counting

Lecture 21: DNF Counting

Lecture 22: GF[2] Polynomial Counting

Lecture 23: Bounded Depth Circuit Counting

References