Laszlo Babai

George and Elizabeth Yovovich Professor

Departments of Computer Science and Mathematics

Interests

Theory

Contact Information

University of Chicago
1100 E 58th Street
Chicago, IL 60637-1588
Office: Ry 164
Phone: (773)702-3486
Fax: (773)702-8487
laci@cs.uchicago.edu

Personal Homepage

http://people.cs.uchicago.edu/~laci

Research

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.

Technical Reports

TR-2003-09

Locally Testable Cyclic Codes. Laszlo Babai; Amir Shpilka; Daniel Stefankovic. 12 August, 2003. Communicated by Laszlo Babai.