Contact Info
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

Theory

The mathematical foundations of computation, including algorithm design, complexity and logic

Labs & Groups

Theoretical Computer Science Group

The Theory group plays a fundamental role in connecting CS with physics, statistics, and other mathematical sciences.

News & Events

Prof László Babai Speaks at ICM’18 About Graph Isomorphism

Oct 04, 2018
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube