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 the asymptotic theory of finite groups (the study of the symmetries of large objects), with an emphasis on the interactions between these fields. Probabilistic methods are common features in my work in each of these areas; linear algebra and number theory are also frequently used. The introduction of the terms "Las Vegas algorithm" and "asymptotic group theory" and the introduction of the concepts of "Arthur-Merlin games" (public-coin interactive proof systems), "holographic proofs" (proofs verifiable by spot-checks), "black-box groups" are among the conceptual highlights. My current focus is on the complexity of the graph isomorphism problem. This long-standing open problem is intimately connected to the asymptotic theory of permutation groups, another area of my continuing interest.