Some Successes and Failures of Algebra in Constructing Extractors

David Zuckerman
University of Texas, Austin
Computer Science Dept

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.

Presentation (PDF File)

Back to Automorphic Forms, Group Theory and Graph Expansion