{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T08:00:48Z","timestamp":1780473648890,"version":"3.54.1"},"reference-count":42,"publisher":"Emerald","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,3,15]]},"abstract":"<jats:p>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 \u201cunconditional derandomization\u201d), and in others it uses computational assumptions, like the existence of 1-way functions (giving \u201cconditional derandomization\u201d).<\/jats:p>\n                  <jats:p>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 \u201cderandomization\u201d 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].<\/jats:p>","DOI":"10.1561\/0400000009","type":"journal-article","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T09:45:04Z","timestamp":1154425504000},"page":"237-301","source":"Crossref","is-referenced-by-count":31,"title":["Pairwise Independence and Derandomization"],"prefix":"10.1108","volume":"1","author":[{"given":"Michael","family":"Luby","sequence":"first","affiliation":[{"name":"Digital Fountain , Fremont, CA,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study , Princeton, NJ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2006,3,15]]},"reference":[{"key":"2026041706435447000_ref001","first-page":"75","article-title":"Two theorems on random polynomial time","volume-title":"FOCS","author":"Adleman","year":"1978"},{"key":"2026041706435447000_ref002","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u221111-Formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Annals of Pure and Applied Logic"},{"key":"2026041706435447000_ref003","first-page":"132","article-title":"Deterministic simulation in LOGSPACE","volume-title":"STOC","author":"Ajtai","year":"1987"},{"issue":"2","key":"2026041706435447000_ref004","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1137\/0217013","article-title":"RSA\/Rabin functions: Certain parts are as hard as the whole","volume":"17","author":"Alexi","year":"1988","journal-title":"SIAM J. on Computing"},{"key":"2026041706435447000_ref005","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","article-title":"A fast and simple randomized parallel algorithm for the maximal independent set problem","volume":"7","author":"Alon","year":"1986","journal-title":"Journal of Algorithms"},{"key":"2026041706435447000_ref006","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","article-title":"Explicit construction of linear sized tolerant networks","volume":"72","author":"Alon","year":"1989","journal-title":"Discrete Math"},{"key":"2026041706435447000_ref007","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA \u2260 NPA \u2260 co \u2013 NPA with probability one","volume":"10","author":"Bennett","year":"1981","journal-title":"Siam J. on Computing"},{"key":"2026041706435447000_ref008","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to generate cryptographically strong sequences of pseudo-random bits","volume":"13","author":"Blum","year":"1982","journal-title":"SIAM J. on Computing"},{"key":"2026041706435447000_ref009","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","article-title":"With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy","volume":"38","author":"Cai","year":"1986","journal-title":"J. of Computer and System Sci."},{"key":"2026041706435447000_ref010","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","article-title":"On the power of two-point sampling","volume":"5","author":"Chor","year":"1989","journal-title":"Journal of Complexity"},{"key":"2026041706435447000_ref011","first-page":"14","article-title":"Dispersers, deterministic amplification, and weak random sources","volume-title":"FOCS","author":"Cohen","year":"1989"},{"key":"2026041706435447000_ref012","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table in O(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"Journal of the ACM"},{"key":"2026041706435447000_ref013","first-page":"260","article-title":"Parity, circuits and the polynomial time hierarchy","volume-title":"FOCS","author":"Furst","year":"1981"},{"issue":"4","key":"2026041706435447000_ref014","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","article-title":"How to construct random functions","volume":"33","author":"Goldreich","year":"1986","journal-title":"J. of ACM"},{"key":"2026041706435447000_ref015","first-page":"25","article-title":"A hard-core predicate for any one-way function","volume-title":"STOC","author":"Goldreich","year":"1989"},{"key":"2026041706435447000_ref016","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic encryption","volume":"28","author":"Goldwasser","year":"1982","journal-title":"J. of Computer and System Sci."},{"key":"2026041706435447000_ref017","first-page":"59","article-title":"Private coins vs public coins in interactive proof systems","volume-title":"STOC","author":"Goldwasser","year":"1986"},{"key":"2026041706435447000_ref018","volume-title":"Computational limitations for small depth circuits","author":"H\u00e5stad","year":"1986"},{"issue":"4","key":"2026041706435447000_ref019","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","article-title":"A pseudo-random generator from any one-way function","volume":"28","author":"Hastad","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"2026041706435447000_ref020","doi-asserted-by":"crossref","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander graphs and their applications","volume-title":"Bulletin of the AMS","author":"Hoory"},{"key":"2026041706435447000_ref021","first-page":"12","article-title":"A pseudo-random generator from any one-way function","volume-title":"STOC","author":"Impagliazzo","year":"1989"},{"key":"2026041706435447000_ref022","first-page":"248","article-title":"How to recycle random bits","volume-title":"FOCS","author":"Impagliazzo","year":"1990"},{"key":"2026041706435447000_ref023","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0885-064X(85)90021-4","article-title":"Monte-carlo algorithms for the planar multiterminal network reliability problem","volume":"1","author":"Karp","year":"1985","journal-title":"J. of Complexity"},{"issue":"3","key":"2026041706435447000_ref024","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","article-title":"Monte-carlo approximation algorithms for enumeration problems","volume":"10","author":"Karp","year":"1989","journal-title":"J. of Algorithms"},{"key":"2026041706435447000_ref025","first-page":"325","article-title":"Expanders, randomness, or time versus space","volume-title":"First Annual Conference on Structure in Complexity Theory","author":"Karp","year":"1986"},{"issue":"2","key":"2026041706435447000_ref026","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.1993.1014","article-title":"Approximating the number of solutions to a GF[2] formula","volume":"14","author":"Karpinski","year":"1993","journal-title":"Journal of Algorithms"},{"key":"2026041706435447000_ref027","first-page":"240","article-title":"Explicit expanders and the ramanujan conjectures","volume":"8","author":"Lubotzky","year":"1988","journal-title":"STOC"},{"issue":"4","key":"2026041706435447000_ref028","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. on Computing"},{"key":"2026041706435447000_ref029","first-page":"51","article-title":"Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators","volume":"24","author":"Margulis","year":"1988","journal-title":"Problemy Peredachi Informatsii"},{"key":"2026041706435447000_ref030","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","article-title":"Pseudorandom bits for constant depth circuits","volume":"1","author":"Nisan","year":"1991","journal-title":"Combinatorica"},{"key":"2026041706435447000_ref031","first-page":"619","article-title":"RL\u2286SC","volume-title":"STOC","author":"Nisan","year":"1992"},{"issue":"2","key":"2026041706435447000_ref032","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","article-title":"Hardness vs. randomness","volume":"49","author":"Nisan","year":"1994","journal-title":"J. of Comp. Sci. and Sys."},{"key":"2026041706435447000_ref033","first-page":"235","article-title":"More deterministic simulation in logspace","volume-title":"STOC","author":"Nisan","year":"1993"},{"key":"2026041706435447000_ref034","volume-title":"Computational complexity","author":"Papadimitriou","year":"1993"},{"key":"2026041706435447000_ref035","volume-title":"Probability theory","author":"Renyi","year":"1970"},{"key":"2026041706435447000_ref036","first-page":"330","article-title":"A complexity theoretic approach to randomness","volume-title":"STOC","author":"Sipser","year":"1983"},{"key":"2026041706435447000_ref037","volume-title":"Introduction to the theory of computation","author":"Sipser","year":"1997"},{"issue":"8","key":"2026041706435447000_ref038","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The complexity of computing the permanent","author":"Valiant","year":"1979","journal-title":"Theoretical Computer Science"},{"key":"2026041706435447000_ref039","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","article-title":"NP is as easy as detecting unique solutions","volume":"47","author":"Valiant","year":"1986","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"2026041706435447000_ref040","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","article-title":"New hash functions and their use in authentication and set equality","volume":"22","author":"Wegman","year":"1981","journal-title":"Journal of Computer and System Sciences"},{"key":"2026041706435447000_ref041","first-page":"80","article-title":"Theory and applications of trapdoor functions","volume-title":"FOCS","author":"Yao","year":"1982"},{"key":"2026041706435447000_ref042","first-page":"1","article-title":"Separating the polynomial-time hierarchy by oracles","volume-title":"FOCS","author":"Yao","year":"1985"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/4\/237\/11524782\/0400000009en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/4\/237\/11524782\/0400000009en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:15Z","timestamp":1777489275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/1\/4\/237\/1360407\/Pairwise-Independence-and-Derandomization"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3,15]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,3,15]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000009","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3,15]]}}}