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 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.

List of Publications

Available in HTML and Postscript.

Technical Reports

TR-2003-09

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