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
2024
2023
2022
2021
2020
IEEE FOCS test of time award
2019
Bruce and Diana Rauner Distinguished Service Professor (2019-current)
2018
2017
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
2014
2013
2012
2011
2010
George and Elizabeth Yovovich Professor (2010-2019)
2009
2008
2007
2006
2005
Quantrell Award for Excellence in undergraduate teaching
2004
2003
2002
2001
2000
1999
Honorary doctorate
1998
Hungarian State Prize
1997
1996
Andre Aisenstadt Chair, Univ. Montreal
1995
1994
1993
Gödel Prize
T.Szele Prize
1992
1991
1990
Corresponding member of the Hungarian Academy of Sciences (elected 1990), full member (elected 1994)
1989
1988
1987
1983
Mathematical Prize, Hungarian Academy of Sciences
