Laszlo Babai

Professor
Department of Computer Science
Professor
Department of Mathematics
Professor
Physical Sciences Collegiate Division

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. Daniel Stefankovic; Amir Shpilka; Laszlo Babai. 12 August, 2003. Communicated by Laszlo Babai.
TR-2001-21
On the number of zero-patterns of a sequence of polynomials. Murali K. Ganapathy; L. Babai; L. Ronyai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-20
Set systems with restricted intersections modulo prime powers. D. Stefankovic; S. Kutin; P. Frankl; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-19
The cost of the missing bit: Communication complexity with help. P. Kimmel; T. Hayes; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-18
Recognizing simplicity of black-box groups and the frequency of {p}-singular elements in affine groups. A. Shalev; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-17
Automorphisms and enumeration of switching classes of tournaments. P. J. Cameron; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-16
Strong bias of group generators: an obstacle to the "product replacement algorithm.". I. Pak; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-15
Stronger separations for random-self-reducibility, rounds, and advice. S. Laplante; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-14
Finite Probability Spaces. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-13
Superpolynomial lower bounds for monotone span programs. Gal, A. Wigderson; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-12
A polynomial-time theory of black box groups I. R. Beals; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-11
Paul Erdos just left town. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-10
Finite and Transfinite Combinatorics. (Tribute to Paul Erdos.). L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-09
Communication complexity. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-08
Short presentations for finite groups. P. P. Palfy; E. M. Luks; W. M. Kantor; A. J. Goodman; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-07
Randomized simultaneous messages: solution of a problem of Yao in communication complexity. P. Kimmel; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-06
Paul Erdos (1913--1996): His Influence on the Theory of Computing. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-05
Randomization in group algorithms: conceptual questions. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-04
The growth rate of vertex-transitive planar graphs. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-03
In and Out of Hungary: Paul Erdos, His Friends, and Times. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-02
A new proof of several inequalities on codes and sets. R. M. Wilson; H. Snevily; L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-2001-01
The Fourier Transform and Equations over Finite Abelian Groups. L. Babai. 1 January, 2001. Communicated by Laszlo Babai.
TR-96-23
Simultaneous Messages vs. Communication. Lokam, S.V.; Kimmel, P.G.; Gal, A.; Babai, L.. 12 November, 1996. Communicated by Laszlo Babai.
TR-96-10
Randomized Simultaneous Messages. Kimmel, Peter G.; Babai, Laszlo. 30 April, 1996. Communicated by Laszlo Babai.
TR-94-23
Multiplicative equations over commuting matrices. Luks, Eugene M.; Ivanyos, Gabor; Cai, Jin-yi; Beals, Robert; Babai, Laszlo. 30 November, 1994. Communicated by Laszlo Babai.
TR-94-22
Simultaneous Messages vs. Communication. Lokam, Satyanarayana V.; Kimmel, Peter G.; Babai, Laszlo. 30 November, 1994. Communicated by Laszlo Babai.
TR-94-10
Automorphism groups, isomorphism, reconstruction*. Babai, Laszlo. 9 June, 1994. Communicated by Laszlo Babai.
TR-94-07
Transparent Proofs and Limits to Approximation. Babai, Laszlo. 9 May, 1994. Communicated by Laszlo Babai.
TR-94-04
Simultaneous Messages vs. Communication. Kimmel, Peter; Babai, Laszlo. 11 March, 1994. Communicated by Laszlo Babai.
TR-93-15
Transparent Proofs and Limits to Approximation. Babai, Laszlo. 1 September, 1993. Communicated by Laszlo Babai.
TR-93-13
On slightly superlinear transparent proofs. Babai, Laszlo; Friedl, Katalin. 16 August, 1993. Communicated by Laszlo Babai.
TR-93-01
Transparent (holographic) proofs. Babai, Laszlo. 6 January, 1993. Communicated by Laszlo Babai.
TR-92-17
Deciding finiteness of matrix groups in deterministic polynomial time. Rockmore, Daniel; Beals, Robert; Babai, Laszlo. 4 September, 1992. Communicated by Laszlo Babai.
TR-92-16
Computing the Composition Factors of Primitive Groups. Seress, Akos; Luks, Eugene M.; Babai, Laszlo. 4 September, 1992. Communicated by Laszlo Babai.
TR-92-11
Short Presentations for Finite Groups. Palfy, P. P.; Luks, E. M.; Kantor, W. M.; Goodman, A.J.; Babai, L.. 15 June, 1992. Communicated by Laszlo Babai.
TR-92-10
On the Abstract Group of Automorphisms. Goodman, Albert J.; Babai, Laszlo. 15 June, 1992. Communicated by Laszlo Babai.
TR-92-02
On the diameter of random Cayley graphs of the symmetric group. Hetyei, G. L.; Babai, L.. 20 January, 1992. Communicated by Laszlo Babai.
TR-91-24
On Faithful Permutation Representations of Small Degree. Goodman, Albert J.; Babai, Laszlo. 15 August, 1991. Communicated by Laszlo Babai.
TR-91-23
On the diameter of permutation groups. Seress, Akos; Babai, Laszlo. 14 August, 1991. Communicated by Laszlo Babai.
TR-91-22
Local expansion of symmetrical graphs. Babai, Laszlo; Szegedy, Mario. 14 August, 1991. Communicated by Laszlo Babai.
TR-91-21
Permutation groups without exponentially many orbits on the power set. Pyber, Laszlo; Babai, Laszlo. 13 August, 1991. Communicated by Laszlo Babai.
TR-91-20
Approximate Representation Theory of Finite Groups. Friedl, Katalin; Babai, Laszlo. 23 July, 1991. Communicated by Laszlo Babai.
TR-91-17
Symmetry and Complexity. Takacsi-Nagy, Pal; Beals, Robert; Babai, Laszlo. 2 May, 1991. Communicated by Laszlo Babai.
TR-91-16
Nearly Linear Time Algorithms for Permutation Groups with a Small Base. Seress, Akos; Finkelstein, Larry; Cooperman, Gene; Babai, Laszlo. 2 May, 1991. Communicated by Laszlo Babai.
TR-91-15
Bounded round interactive proofs in finite groups. Babai, Laszlo. 15 April, 1991. Communicated by Laszlo Babai.
TR-91-14
Graph with Given Automorphism Group and Few Edge Orbits. Lovasz, Laszlo; Goodman, Albert J.; Babai, Laszlo. 12 April, 1991. Communicated by Laszlo Babai.
TR-91-12
Subdirect Reducible Groups and Edge-Minimal Graphs with Given Automorphism Group. Goodman, Albert J.; Babai, Laszlo. 5 April, 1991. Communicated by Laszlo Babai.
TR-91-10
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. Lund, Carsten; Fortnow, Lance; Babai, Laszlo. 5 April, 1991. Communicated by Laszlo Babai.
TR-91-09
Arithmetization: A New Method in Structural Complexity Theory. Fortnow, Lance; Babai, Laszlo. 5 April, 1991. Communicated by Laszlo Babai.
TR-91-08
Checking Computations in Polylogarithmic Time. Szegedy, Mario; Levin, Leonid A.; Fortnow, Lance; Babai, Laszlo. 22 March, 1991. Communicated by Laszlo Babai.
TR-91-06
Checking Computations in Polylogarithmic Time. Szegedy, Mario; Levin, Leonid A.; Fortnow, Lance; Babai, Laszlo. 7 March, 1991. Communicated by Laszlo Babai.
TR-91-05
Fast Monte Carlo Algorithms for Permutation Groups. Seress, Akos; Luks, Eugene; Finkelstein, Larry; Cooperman, Gene; Babai, Laszlo. 7 March, 1991. Communicated by Laszlo Babai.
TR-91-03
Vertex-Transitive Graphs and Vertex-Transitive Maps. Babai, Laszlo. 11 February, 1991. Communicated by Laszlo Babai.
TR-91-02
Computational Complexity in Finite Groups. Babai, Laszlo. 6 February, 1991. Communicated by Laszlo Babai.
TR-90-31B
Local expansion of vertex-transitive graphs and random generation in finite groups. Babai, Laszlo. 16 October, 1990. Communicated by Laszlo Babai.
TR-90-15
E-mail and the Unexpected Power of Interaction. Babai, Laszlo. 24 April, 1990. Communicated by Laszlo Babai.
TR-90-14
BPP has Weak Subexponential Time Simulations unless EXPTIME has Publishable Proofs. Fortnow, Lance; Babai, Laszlo; Wigderson, Avi; Nisan, Noam. 23 April, 1990. Communicated by Laszlo Babai.
TR-90-10
Vertex-Transitive Graphs and Vertex-Transitive Maps. Babai, Laszlo. 15 March, 1990. Communicated by Laszlo Babai.