LBLászló Babai
László Babai
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
László Babai has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Cheryl E. Praeger
The University of Western Australia
2 shared publications - John Wilmes
University of Chicago
2 shared publications - Robert Arnott Wilson
School of Mathematical Sciences, Queen Mary University of London 3 , London E1 4NS, United Kingdom
2 shared publications - Angela Wu
University of Chicago
1 shared publication - Anna Gál
University of Texas at Austin
1 shared publication - Avi Wigderson
Institute for Computer Science, Hebrew University, Givat Ram, Jerusalem, Israel
1 shared publication
Latest Publications
- 1 October 2022
- Published by Elsevier in Journal of Algebra
- Vol. 607, 64-106
Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed
- 1 October 2022
- Published by Elsevier in Journal of Algebra
- Vol. 607, 64-106
Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed
- Open Access
List-decoding homomorphism codes with arbitrary codomains
The codewords of the homomorphism code $\operatorname{aHom}(G,H)$ are the affine homomorphisms between two finite groups, $G$ and $H$, generalizing Hadamard codes. Following the work of Goldreich--Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to $\textsf{mindist}$, the minimum distance of the code. In particular, for the first time, we do not require either $G$ or $H$ to be solvable. Specifically, we demonstrate a $\operatorname{poly}(1/\varepsilon)$ bound on the list size, i.e., on the number of codewords within distance $(\textsf{mindist}-\varepsilon)$ from any received word, when $G$ is either abelian or an alternating group, and $H$ is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case. The abelian vs. arbitrary result then permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (i.e., when the codomain is a symmetric group $S_m$) under the restriction that the domain $G=A_n$ is paired with codomain $H=S_m$ satisfying $m < 2^{n-1}/\sqrt{n}$. The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018). However, we also introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list.Open AccessList-decoding homomorphism codes with arbitrary codomains
The codewords of the homomorphism code $\operatorname{aHom}(G,H)$ are the affine homomorphisms between two finite groups, $G$ and $H$, generalizing Hadamard codes. Following the work of Goldreich--Levin (1989), Grigorescu et al. (2006), Dinur et al. (2008), and Guo and Sudan (2014), we further expand the range of groups for which local list-decoding is possible up to $\textsf{mindist}$, the minimum distance of the code. In particular, for the first time, we do not require either $G$ or $H$ to be solvable. Specifically, we demonstrate a $\operatorname{poly}(1/\varepsilon)$ bound on the list size, i.e., on the number of codewords within distance $(\textsf{mindist}-\varepsilon)$ from any received word, when $G$ is either abelian or an alternating group, and $H$ is an arbitrary (finite or infinite) group. We conjecture that a similar bound holds for all finite simple groups as domains; the alternating groups serve as the first test case. The abelian vs. arbitrary result then permits us to adapt previous techniques to obtain efficient local list-decoding for this case. We also obtain efficient local list-decoding for the permutation representations of alternating groups (i.e., when the codomain is a symmetric group $S_m$) under the restriction that the domain $G=A_n$ is paired with codomain $H=S_m$ satisfying $m < 2^{n-1}/\sqrt{n}$. The limitations on the codomain in the latter case arise from severe technical difficulties stemming from the need to solve the homomorphism extension (HomExt) problem in certain cases; these are addressed in a separate paper (Wuu 2018). However, we also introduce an intermediate "semi-algorithmic" model we call Certificate List-Decoding that bypasses the HomExt bottleneck and works in the alternating vs. arbitrary setting. A certificate list-decoder produces partial homomorphisms that uniquely extend to the homomorphisms in the list. - 20 June 2015
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 43 (4) , 771-782
Asymptotic Delsarte cliques in distance-regular graphs
- 20 June 2015
- Published by Springer Nature in Journal of Algebraic Combinatorics
- Vol. 43 (4) , 771-782
Asymptotic Delsarte cliques in distance-regular graphs
- Open Access
Asymptotic Delsarte cliques in distance-regular graphs
We give a new bound on the parameter $\lambda$ (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph $G$, improving and generalizing bounds for strongly regular graphs by Spielman (1996) and Pyber (2014). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai, Chen, Sun, Teng, Wilmes 2013). The proof is based on a clique geometry found by Metsch (1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch's result: if $k\mu = o(\lambda^2)$ then each edge of $G$ belongs to a unique maximal clique of size asymptotically equal to $\lambda$, and all other cliques have size $o(\lambda)$. Here $k$ denotes the degree and $\mu$ the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch's cliques are "asymptotically Delsarte" when $k\mu = o(\lambda^2)$, so families of distance-regular graphs with parameters satisfying $k\mu = o(\lambda^2)$ are "asymptotically Delsarte-geometric."Open AccessAsymptotic Delsarte cliques in distance-regular graphs
We give a new bound on the parameter $\lambda$ (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph $G$, improving and generalizing bounds for strongly regular graphs by Spielman (1996) and Pyber (2014). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai, Chen, Sun, Teng, Wilmes 2013). The proof is based on a clique geometry found by Metsch (1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch's result: if $k\mu = o(\lambda^2)$ then each edge of $G$ belongs to a unique maximal clique of size asymptotically equal to $\lambda$, and all other cliques have size $o(\lambda)$. Here $k$ denotes the degree and $\mu$ the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch's cliques are "asymptotically Delsarte" when $k\mu = o(\lambda^2)$, so families of distance-regular graphs with parameters satisfying $k\mu = o(\lambda^2)$ are "asymptotically Delsarte-geometric." - 11 April 2013
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 88 (1) , 202-226
Proportions of r -regular elements in finite classical groups
- 11 April 2013
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 88 (1) , 202-226
Proportions of r -regular elements in finite classical groups
- Open Access
Proportions of r-regular elements in finite classical group
For a prime $r$, we obtain lower bounds on the proportion of $r$-regular elements in classical groups and show that these lower bounds are the best possible lower bounds that do not depend on the order of the defining field. Along the way, we also provide new upper bounds and answer some open questions of the first author, P\'{a}lfy and Saxl.Open AccessProportions of r-regular elements in finite classical group
For a prime $r$, we obtain lower bounds on the proportion of $r$-regular elements in classical groups and show that these lower bounds are the best possible lower bounds that do not depend on the order of the defining field. Along the way, we also provide new upper bounds and answer some open questions of the first author, P\'{a}lfy and Saxl. - Open Access
- 7 January 2009
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R123
Spectral Extrema for Graphs: The Zarankiewicz Problem
Let $G$ be a graph on $n$ vertices with spectral radius $\lambda$ (this is the largest eigenvalue of the adjacency matrix of $G$). We show that if $G$ does not contain the complete bipartite graph $K_{t ,s}$ as a subgraph, where $2\le t \le s$, then $$\lambda \le \Big((s-1)^{1/t }+o(1)\Big)n^{1-1/t }$$ for fixed $t$ and $s$ while $n\to\infty$. Asymptotically, this bound matches the Kővári-Turán-Sós upper bound on the average degree of $G$ (the Zarankiewicz problem).- 7 January 2009
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R123
Open AccessSpectral Extrema for Graphs: The Zarankiewicz Problem
Let $G$ be a graph on $n$ vertices with spectral radius $\lambda$ (this is the largest eigenvalue of the adjacency matrix of $G$). We show that if $G$ does not contain the complete bipartite graph $K_{t ,s}$ as a subgraph, where $2\le t \le s$, then $$\lambda \le \Big((s-1)^{1/t }+o(1)\Big)n^{1-1/t }$$ for fixed $t$ and $s$ while $n\to\infty$. Asymptotically, this bound matches the Kővári-Turán-Sós upper bound on the average degree of $G$ (the Zarankiewicz problem). - 1 March 2007
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 158 (1) , 193-203
Finite groups of uniform logarithmic diameter
- 1 March 2007
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 158 (1) , 193-203
Finite groups of uniform logarithmic diameter
- 1 July 2001
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 95 (1) , 39-73
Set Systems with Restricted Intersections modulo Prime Powers
- 1 July 2001
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 95 (1) , 39-73
Set Systems with Restricted Intersections modulo Prime Powers
- Open Access
- 1 January 2000
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 7 (1) , R38
Automorphisms and Enumeration of Switching Classes of Tournaments.
Two tournaments $T_1$ and $T_2$ on the same vertex set $X$ are said to be switching equivalent if $X$ has a subset $Y$ such that $T_2$ arises from $T_1$ by switching all arcs between $Y$ and its complement $X\setminus Y$. The main result of this paper is a characterisation of the abstract finite groups which are full automorphism groups of switching classes of tournaments: they are those whose Sylow 2-subgroups are cyclic or dihedral. Moreover, if $G$ is such a group, then there is a switching class $C$, with Aut$(C)\cong G$, such that every subgroup of $G$ of odd order is the full automorphism group of some tournament in $C$. Unlike previous results of this type, we do not give an explicit construction, but only an existence proof. The proof follows as a special case of a result on the full automorphism group of random $G$-invariant digraphs selected from a certain class of probability distributions. We also show that a permutation group $G$, acting on a set $X$, is contained in the automorphism group of some switching class of tournaments with vertex set $X$ if and only if the Sylow 2-subgroups of $G$ are cyclic or dihedral and act semiregularly on $X$. Applying this result to individual permutations leads to an enumeration of switching classes, of switching classes admitting odd permutations, and of tournaments in a switching class. We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting automorphism groups (by a theorem of Fraïssé).- 1 January 2000
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 7 (1) , R38
Open AccessAutomorphisms and Enumeration of Switching Classes of Tournaments.
Two tournaments $T_1$ and $T_2$ on the same vertex set $X$ are said to be switching equivalent if $X$ has a subset $Y$ such that $T_2$ arises from $T_1$ by switching all arcs between $Y$ and its complement $X\setminus Y$. The main result of this paper is a characterisation of the abstract finite groups which are full automorphism groups of switching classes of tournaments: they are those whose Sylow 2-subgroups are cyclic or dihedral. Moreover, if $G$ is such a group, then there is a switching class $C$, with Aut$(C)\cong G$, such that every subgroup of $G$ of odd order is the full automorphism group of some tournament in $C$. Unlike previous results of this type, we do not give an explicit construction, but only an existence proof. The proof follows as a special case of a result on the full automorphism group of random $G$-invariant digraphs selected from a certain class of probability distributions. We also show that a permutation group $G$, acting on a set $X$, is contained in the automorphism group of some switching class of tournaments with vertex set $X$ if and only if the Sylow 2-subgroups of $G$ are cyclic or dihedral and act semiregularly on $X$. Applying this result to individual permutations leads to an enumeration of switching classes, of switching classes admitting odd permutations, and of tournaments in a switching class. We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting automorphism groups (by a theorem of Fraïssé).