Pairwise Independence and Derandomization

Author(s): Michael Luby;Avi Wigderson

Source:
    Journal:Foundations and Trends® in Theoretical Computer Science
    ISSN Print:1551-305X,  ISSN Online:1551-3068
    Publisher:Now Publishers
    Volume 1 Number 4,

Document Type: Article
Pages: 65 (237-301)
DOI: 10.1561/0400000009

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”).

Full Text