László Babai's selected publications

Acknowledgment and disclaimer. Research leading to papers indicated by (*) has been partially supported by NSF grants. The grant number is indicated next to the bibliographic data of each paper. Any opinions, findings and conclusions or recommendations expressed in those papers are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).

• L. Babai, B. Guiduli: Spectral extrema for graphs: the Zarankiewicz problem. Electronic J. of Combinatorics 16/1 (Sep 2009) R123 (8pp)
• (*) L. Babai, R. Beals, Á Seress: Polynomial-time Theory of Matrix Groups. In: Proc. 41st ACM STOC, 2009, pp. 55-64. (NSF Grant # CCF-0830370)
• (*) L. Babai, P. P. Pálfy, J. Saxl: On the number of p-regular elements in finite simple groups. LMS Journal of Computation and Mathematics 12 (2009) 82-119. (NSF Grants # CCR-9732205 and CCF-0830370)
• (*) L. Babai, P. Codenotti: Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time. (EXTENDED ABSTRACT) In: Proc. 39th Ann. IEEE Symp. on Theory of Computing (FOCS'08), IEEE Comp. Soc. Press 2008, 667-676. (NSF Grant # CCF-0830370)
• L. Babai, P. Felzenszwalb: Computing rank-convolutions with a mask. ACM Transactions on Algorithms, to appear
• L. Babai: Coset Intersection in Moderately Exponential Time. April 2008. Submitted for publication.
• L. Babai, N. Nikolov, L. Pyber: Product growth and mixing in finite groups. (EXTENDED ABSTRACT) In: Proc. 19th Ann. Symp. on Discrete Algorithms (SODA'08), ACM--SIAM 2008, 248--257. (Full paper in preparation.)
• M. Abért, L. Babai: Finite groups of uniform logarithmic diameter. Israel J. Math. 158 (2007), 193--203.
• L. Babai, I. Gorodezky: Sandpile transience on the grid is polynomially bounded. In: Proc. 18th Ann. Symp. on Discrete Algorithms (SODA'07), ACM--SIAM 2007, pp. 627-636.
• L. Babai, T. Hayes: The probability of generating the symmetric group when one of the generators is random. Publ. Math. Debrecen 69/3 (2006), 271-280.
• L. Babai: On the diameter of Eulerian orientations of graphs. In: Proc. 17th Ann. Symp. on Discrete Algorithms (SODA'06), ACM--SIAM 2006, pp. 822--831
• L. Babai, A. Shpilka, D. Štefankovič: Locally testable cyclic codes. IEEE Trans. on Information Theory 51(8) (2005), 2849--2858. (Extended abstract: Proc. 44th IEEE FOCS, 2003, pp. 116--125.)
• L. Babai, T. Hayes: Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. In: Proc. 16th Ann. Symp. on Discrete Algorithms (SODA'05), ACM--SIAM 2005, pp.1057--1066
• L. Babai, A. Gál, P. Kimmel, Satya V. Lokam: Communication Complexity of Simultaneous Messages. SIAM J. Comp. 33 (2004), pp. 137--166.
• L. Babai, D. Štefankovič: Simultaneous Diophantine Approximation with Excluded Primes. In: Proc. 15th Ann. Symp. on Discrete Algorithms (SODA'04), ACM--IEEE 2004, pp. 1123--1129
• (*) L. Babai, I. Pak: Strong bias of group generators: an obstacle to the ``product replacement algorithm.'' J. Algorithms 50 (2004), pp. 215--231 (NSF Grant # CCR-9732205)
• (*) L. Babai, W. M. Kantor, P. P. Pálfy, Á. Seress: Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5 (2002), 383--401 (NSF Grant # CCR-9732205)
• L. Babai, T. Hayes, P. Kimmel: The cost of the missing bit: Communication complexity with help. Combinatorica 21 (2001), 455-488
• L. Babai, P. Frankl, S. Kutin, D. Štefankovič: Set systems with restricted intersections modulo prime powers. J. Combinatorial Theory - A 95 (2001), 39--73.
• (*) L. Rónyai, L. Babai, Murali K. Ganapathy: On the number of zero-patterns of a sequence of polynomials. J. Amer. Math. Soc. 14 (2001), 717--735. (NSF Grant # CCR-9732205)
• (*) L. Babai, A. Shalev: Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups. In: Groups and Computation III. Proc. 1999 Workshop at the Ohio State University (W. M. Kantor and Ákos Seress, eds.) Ohio State University Mathematical Research Institute Publications 8, deGruyter, Berlin -- New York, 2001, pp. 39--62. (NSF Grant # CCR-9732205)
• L. Babai, R. Beals: A polynomial-time theory of black box groups I. In: Groups St Andrews 1997 in Bath, I (C.M. Campbell, E.F. Robertson, N. Ruskuc, G. C. Smith, eds.), London Math. Soc. Lect. Notes 260, Cambr. U. Press, 1999, pp. 30-64.
• L. Babai, A. Gál, A. Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica 19 (1999), 301--320.

My 20th century papers