Videos

January 5, 2010

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