January 5, 2010
- George and Elizabeth Yovovich Professor
- Departments of Computer Science and Mathematics
University of Chicago
1100 E 58th Street
Chicago, IL 60637-1588
Office: Ry 164
I work in the fields of theoretical computer science and discrete mathematics; more specifically in computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields. Asymptotic questions and probabilistic methods are common features in my work in each of these areas. The introduction of Las Vegas algorithms, interactive proofs, holographic proofs (proofs verifiable by spotchecks) are among the conceptual highlights. A recent example: methods of the complexity theories of Boolean circuits and branching programs have been brought to bear on the analysis of a popular random sampling technique in computational group theory.
List of Publications
Available in HTML and Postscript.