Automorphism groups, isomorphism, reconstruction

By László Babai. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, background): “…a polynomial-time algorithm for the graph isomorphism problem—the problem of deciding whether two given graphs are the same up to a change of labels—which from a theoretical perspective ranks among the most extensively studied computational problems [2] [3] [4] [18] [19] [24] [36] [39].”
Four Questions on Birkhoff Polytope (2000, background): “Before we finish, let us recall an old conjecture which states that if the size of the generating set R Sn is polynomial in n, then a mixing time mix for a random walk on Sn is also polynomial (cf. [ 3 , 7, 20]).”
Logical complexity of graphs: a survey (2010, methodology): “isfeiler-Lehman algorithm. The eﬃciency of this method depends much on the logical complexity of input graphs. For the history of this approach to the graph isomorphism problem we refer the reader to [5, 15]. We will abbreviate k-dimensional Weisfeiler-Lehman algorithm by k-dim WL. The 1-dim WL is c”
WHAT DO WE KNOW ABOUT THE PRODUCT REPLACEMENT ALGORITHM (2009, methodology): “7Of course, the use of the \Erd} os-R enyi machine" has an important theoretical and perhaps practical advantage (see [Bb2, Bb4 ]).”
Hodge Laplacians on graphs (2015, background): “The graph isomorphism problem, an open problem in computer science, asks whether there is a polynomial-time algorithm for deciding if two given graphs are isomorphic [5].”
Infinite Hamilton cycles in squares of locally finite graphs (2009, background): “It is a well-known conjecture (apparently first stated in [28], see [2] for more) that every finite connected Cayley graph has a Hamilton cycle.”
On the Universality of Invariant Networks (2019, background): “Groups for which the condition in theorem 3 holds are called 2-closed and were ﬁrst introduced by (Wielandt, 1969) (see (Babai, 1995) for further study).”