Source author record

László Babai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms math.GR Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Graph Isomorphism in Quasipolynomial Time

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial ( $\exp((\log n)^{O(1)})$ ) time. The best previous bound for GI was $\exp(O(\sqrt{n\log n}))$ , where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp(\tilde{O}(\sqrt{n}))$ , where $n$ is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism ϕ that maps a given permutation group $G$ onto $S_k$ or $A_k$ , the symmetric or alternating group of degree $k$ , where $k$ is not too small. We say that an element $x$ in the permutation domain on which $G$ acts is affected by ϕ if the ϕ-image of the stabilizer of $x$ does not contain $A_k$ . The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.

preprint2015arXiv

Asymptotic Delsarte cliques in distance-regular graphs

We give a new bound on the parameter $λ$ (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μ= o(λ^2)$ then each edge of $G$ belongs to a unique maximal clique of size asymptotically equal to $λ$ , and all other cliques have size $o(λ)$ . Here $k$ denotes the degree and $μ$ 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μ= o(λ^2)$ , so families of distance-regular graphs with parameters satisfying $kμ= o(λ^2)$ are "asymptotically Delsarte-geometric."

preprint2014arXiv

Element order versus minimal degree in permutation groups: an old lemma with new applications

In this note we present a simplified and slightly generalized version of a lemma the authors published in 1987. The lemma as stated here asserts that if the order of a permutation of $n$ elements is greater than $n^α$ then some non-identity power of the permutation has support size less than $n/α$ . The original version made an unnecessary additional assumption on the cycle structure of the permutation; the proof of the present cleaner version follows the original proof verbatim. Application areas include parallel and sequential algorithms for permutation groups, the diameter of Cayley graphs of permutation groups, and the automorphisms of structures with regularity constraints such as Latin squares, Steiner 2-designs, and strongly regular graphs. This note also serves as a modest tribute to the junior author whose untimely passing is deeply mourned.

preprint2012arXiv

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álfy and Saxl.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.