Smoothed analysis for graph isomorphism

Zoom Link

From a theoretical point of view, graph isomorphism testing is a notoriously difficult problem, with no known polynomial-time algorithm. However, from a practical point of view, the problem is essentially solved: various elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow, which shows that one of the simplest imaginable algorithms (underpinning all algorithms used in practice) is very effective "on average", in the sense that it can be used to distinguish a typical outcome of a random graph G(n,1/2) from any other graph.

We improve the Babai-Erdős-Selkow theorem in a few directions. In particular, in accordance with the smoothed analysis philosophy of Spielman and Teng, one of our main results is that for any graph G, simple combinatorial algorithms become effective after a tiny random perturbation to G (specifically, the addition and removal of about n random edges).

Joint work with Michael Anastos and Benjamin Moore.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.