Contact Info
Email
Phone
(773) 702-3486
Office
Crerar 242
Research
Focus Areas: Discrete Mathematics, Theory
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.
Research
Labs & Groups
Theoretical Computer Science Group
The Theory group plays a fundamental role in connecting CS with physics, statistics, and other mathematical sciences.
Awards & Honors
2020
IEEE FOCS test of time award
2019
Bruce and Diana Rauner Distinguished Service Professor (2019-current)
2016
Knuth Prize
Dijkstra Prize in Distributed Computing
ACM SIGACT Distinguished Service Award
ACM STOC 2016 Best Paper Award
2015
Fellow of the American Academy of Arts and Science
2010
George and Elizabeth Yovovich Professor (2010-2019)
2005
Quantrell Award for Excellence in undergraduate teaching
1999
Honorary doctorate
1998
Hungarian State Prize
1996
Andre Aisenstadt Chair, Univ. Montreal
1993
Gödel Prize
T.Szele Prize
1990
Corresponding member of the Hungarian Academy of Sciences (elected 1990), full member (elected 1994)
1983
Mathematical Prize, Hungarian Academy of Sciences
