Abstract
Some Successes and Failures of Algebra in Constructing Extractors
David Zuckerman
University of Texas at Austin
A randomness extractor is a procedure to extract randomness from a defective random source, using some additional truly random bits. Extractors have had numerous applications in computer science, some of which arise because they can be viewed as bipartite graphs with certain expansion properties. We point out that eigenvalues fail to certify that a graph is an extractor or even its weaker cousin, a disperser. We then survey recent algebraic constructions of extractors.
No video available