László Babai's recent publications

Acknowledgment and disclaimer. Research leading to papers marked 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ászló Babai, John Wilmes: Quasipolynomial-Time Canonical Form for Steiner Designs. In: Proc. 45th ACM STOC, 2013, to appear. (NSF Grant # CCF-1017781)
• (*) László Babai, Paolo Codenotti, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract). In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62 DOI: 10.1007/978-3-642-31594-7_5 (NSF Grant # CCF-1017781)
• (*) László Babai, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with Abelian Sylow Towers. In: Proc. 29th Ann. Symp. on Theoretical Aspects of Comp. Sci. (STACS'12), Schloss Dagstuhl--Leibniz-Zentrum für Informatik 14, 2012, pp. 453-464 DOI:10.4230/LIPIcs.STACS.2012.453 (NSF Grant # CCF-1017781)
• (*) László Babai, Paolo Codenotti, Joshua Grochow, Youming Qiao: Code Equivalence and Group Isomorphism. In: Proc. 22nd Ann. Symp. on Discrete Algorithms (SODA'11), ACM-SIAM, 2011, pp. 1395-1408 (NSF Grants # CCF-0830370 and CCF-1017781) SIAM
• László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun: Weights of Exact Threshold Functions. In: Proc. 35th Internat. Symp. on Mathematical Foundations of Computer Science (MFCS'10) LNCS, Springer 2010, pp. 66-77. DOI: 10.1007/978-3-642-15155-2_8
• (*) László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the Distribution of Prime Numbers. In: Proc. 27th Ann. Symp. on Theoretical Aspects of Comp. Sci. (STACS 2010), Schloss Dagstuhl Online Publ. 2010, pp. 71--82. DOI: 10.4230/LIPIcs.STACS.2010.2445 (NSF Grant # CCF-0830370)
• László Babai, Pedro Felzenszwalb: Computing rank-convolutions with a mask. ACM Transactions on Algorithms 6/1, 2009, pp 20:1-20:13. DOI: 10.1145/1644015.1644035
• László Babai, Barry Guiduli: Spectral extrema for graphs: the Zarankiewicz problem. Electronic J. of Combinatorics 16/1 (Sep 2009) R123 (8pp)
• (*) László Babai, Robert Beals, Ákos Seress: Polynomial-time Theory of Matrix Groups. (Extended abstract.) In: Proc. 41st ACM STOC, 2009, pp. 55-64. (NSF Grant # CCF-0830370)
• (*) László Babai, Péter P. Pálfy, Jan 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ászló Babai, Paolo 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: 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. (Extended abstract.) 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. (Extended abstract.) 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. (Extended abstract.) 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. (Extended abstract.) 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, R. Beals, Á. Seress: On the diameter of the symmetric group: polynomial bounds. In: Proc. 15th Ann. Symp. on Discrete Algorithms (SODA'04), ACM--IEEE 2004, pp. 1108--1112 (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