László Babai
George and Elizabeth Yovovich Professor,
Departments of Computer Science and Mathematics
Research Interests: Theory, Discrete Mathematics
Research
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.
Jonathan Baker
PhD Student