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

Copyright warning. Copyright to the papers accessible from this website belongs to various entities which use different copyright formulas. Private use is permitted in all cases, instructional use is permitted in most cases. Proper attribution (authors, venue, bibliographic data) is required in all cases when used in printed/posted material, including instructional use. When using this material, please observe the copyright restrictions. Starting with 2013, the items below indicate the copyright owner. Regarding the papers of which the copyright is owned by the author(s), including otherwise unpublished manuscripts, copyright is hereby licensed under the "Creative Commons Attribution License (CC-BY)."

• László Babai: Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed. J. Algebra 607 (2022), 64-106.   (© Elsevier)   DOI: 10.1016/j.jalgebra.2021.10.033   arXiv   (NSF Grant #CCF-1718902)
• László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, and Xiaoming Sun: Weights of Exact Threshold Functions. Izv. Rossiiskoi Akad. Nauk, Ser. Mat., Vol. 85, No. 5, 2021 (in Russian) (journal version of MFCS 2010 paper)
• László Babai and Bohdan Kivva: Matrix Rigidity Depends on the Target Field.   In: 36th Computational Complexity Conf. (CCC'21), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021, pp. 41:1-41:26.   (© Authors CC-BY)   DOI: 10.4230/LIPIcs.CCC.2021.41   (NSF Grant #CCF-1718902)
• László Babai: Canonical form for graphs in quasipolynomial time: preliminary report In: Proc. 51st ACM STOC, 2019, pp 1237-1246.   DOI: 10.1145/3313276.3316356   (NSF Grant #CCF-1718902) (© ACM Press)
• László Babai, Timothy J. F. Black, and Angela Wuu: List-Decoding Homomorphism Codes with Arbitrary Codomains.   In: Approximation, Randomization, and Combinatorial Optimization: Proc. RANDOM'18 Workshop, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, pp. 29-1:29-18.   (© Authors CC-BY)   DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.29   (NSF Grants # CCF-1423309 and CCF-1718902)
• László Babai: Primitive coherent configurations and the order of uniprimitive permutation groups (© Author CC-BY)
  (This is an updated exposition of the author's 1981 paper "On the order of uniprimitive permutation groups," Annals of Math. 113 (1981) 553-568.)
• (*) László Babai: Groups, Graphs, Algorithms: The Graph Isomorphism Problem. Proc. ICM 2018, Rio de Janeiro, Vol. 3, pp. 3319-3336.     (Official version, for ICM'18 participants only)   DOI: 10.1142/9789813272880_0183   ISBN: 978-981-3272-87-3     Here is the pre-publication version (© Author CC-BY)   (NSF Grants # CCF-1423309 and CCF-1718902)
• László Babai: On the degrees of non-split extensions by an alternating group. Manuscript, July 2017. 6 pages
• László Babai: Graph isomorphism in quasipolynomial time [extended abstract] In: Proc. 48th ACM STOC, 2016, pp 684-697.   DOI: 10.1145/2897518.2897542   (NSF Grant # CCF-1423309) (© ACM Press)
• (*) László Babai: Graph Isomorphism in quasipolynomial time. E-print: arXiv:1512.03547.
• László Babai, Peter J. Cameron: Most primitive groups are full automorphism groups of edge-transitive hypergraphs.     J. Algebra, Vol. 421 (2015) (Ákos Seress memorial issue), pp. 512-523 © Elsevier DOI
• (*) László Babai: On the Automorphism Groups of Strongly Regular Graphs II.     J. Algebra, Vol. 421 (2015) (Ákos Seress memorial issue), pp. 560-578 © Elsevier DOI (NSF Grant # CCF-1017781)
• (*) László Babai, Ákos Seress: Element order versus minimal degree in permutation groups: an old lemma with new applications. E-print: arXiv:1401.0481. January 2014. 6 pages. (NSF Grant # CCF-1017781) (© Authors CC-BY)
• (*) László Babai, John Wilmes: Asymptotic Delsarte Cliques in Distance-Regular Graphs. Manuscript, preliminary version. October 2013. (NSF Grant # CCF-1017781) (© Authors CC-BY)
• László Babai, Denis Pankratov: There are no zero-hard problems in multiparty communication complexity. Manuscript, preliminary version. October 2013. (© Authors CC-BY)
• (*) László Babai: Entropy Versus Pairwise Independence. Manuscript, preliminary version. August 2013. (NSF Grant # CCF-1017781) (© Author CC-BY)
• (*) László Babai: On the Automorphism Groups of Strongly Regular Graphs I. In: Proc. 5th Innovations in Theoretical Comp. Sci. conf. (ITCS'14), ACM Press, January 2014, pp 359-368. DOI: 10.1145/2554797.2554830 (NSF Grant # CCF-1017781) (© ACM Press)
• (*) László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes: Faster Canonical Forms for Strongly Regular Graphs (Extended Abstract). In: Proc. 54th IEEE FOCS, pp. 157-166, 2013. (NSF Grant # CCF-1017781) (© IEEE Computer Society Press) Invited to SIAM J. Comp. Special Issue.
• (*) László Babai, Simon Guest, Cheryl E. Praeger, Robert A. Wilson: Proportion of r-regular elements in finite classical groups. J. London Math. Soc. 88(1) (2013) 202-226. (NSF Grant # CCF-1017781) (© London Math. Soc.)
• (*) László Babai, John Wilmes: Quasipolynomial-Time Canonical Form for Steiner Designs. In: Proc. 45th ACM STOC, 2013, pp. 261-270. (NSF Grant # CCF-1017781) (© ACM Press)
• (*) 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.

Automorphism groups, isomorphism, reconstruction.    (pre-publication version, 1994, 73pp text + 19pp bibliography)
Final published paper appears in       R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, Chapter 27, pages 1447-1540. North-Holland - Elsevier, 1995.     (© Elsevier)

Biography of Paul Erdös

L. Babai: In and out of Hungary: Paul Erdös, his friends, and times.
In D. Miklós, V. T. Sós, and T. Szönyi, editors
Combinatorics: Paul Erdös Is Eighty
Vol. 2 of Bolyai Society Mathematical Studies, pages 7-95. J. Bolyai Mathematical Society, Budapest, 1996
(prepublication version, without the photos)

My 20th century papers

Video recordings of recent presentations

• Graph isomorphism in quasipolynomial time I: The Local Certificates algorithm First of a series of four seminar lectures at The University of Chicago. "Combinatorics and Theoretical Computer Science" Seminar, November 10, 2015, Kent 120 (attended by over 200). An unofficial previously posted version of the same lecture got more than twice as many viewings.
• Graph isomorphism in quasipolynomial time II: The Design Lemma Third of a series of four seminar lectures at the University of Chicago. "Combinatorics and Theoretical Computer Science" Seminar, November 24, 2015, Ryerson 251. (The second lecture, titled "A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem" held in Ryerson 251 in the "Group Theory" seminar on November 12, 2015, was not recorded. The last lecture of the series, titled "Graph isomorphism in quasipolynomial time III: Split-or-Johnson," was held in Ryerson 251 on December 1, 2015; the recording was not posted.)
• Graph Isomorphism in Quasipolynomial Time. Colloquium lecture at the Rényi Institute, Budapest, January 4, 2016. Attended by over 100. (Not recorded were two more lectures the same day: a 90-minute lecture in the Algebra seminar, and a four and a half-hour lecture in the Abért--B. Szegedy combinatorics research seminar.)
• Graph isomorphism in quasipolynomial time I First of two lectures at the Institute for Advanced Study, Princeton, February 29, 2016. (A copy of this video appeared previously here.)
• Graph isomorphism in quasipolynomial time II Second of two lectures at the Institute for Advanced Study, Princeton, March 1, 2016. (A copy of this video appeared previously here.)
• Finite permutation groups and the Graph Isomorphism problem 1 Israel Institute for Advanced Studies, Jerusalem, November 28, 2016. First of two lectures at the "60 Faces of Groups" conference, celebrating Alex Lubotzky's 60th birthday
• Finite permutation groups and the Graph Isomorphism problem 2 Israel Institute for Advanced Studies, Jerusalem, November 28, 2016.
• Symmetry vs. Regularity I   First of two lectures given at the "Current Developments in Mathematics" workshop at Harvard, December 17, 2016.
• Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs   First of two lectures at the "Structure vs. Randomness" workshop at the Simons Institute for the Theory of Computing, Berkeley CA, April 12, 2017
• Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs   Second of two lectures at the "Structure vs. Randomness" workshop at the Simons Institute for the Theory of Computing, Berkeley CA, April 12, 2017
• Global symmetry from local information: The Graph Isomorphism Problem   Lecture at ICM 2018 (International Congress of Mathematicians), Rio de Janeiro, August 3, 2018, in a joint session of the "Combinatorics" and "Mathematical aspects of computer science" sections.