Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a canonical labeling, which is a labeling of the vertices of the graph that is invariant under isomorphism. Our technical focus is on the average-case setting, where we settle the question of low-depth canonical labelings in sparse random graphs $G(n,p_n)$ with $p_n = o(1)$. Moreover, our techniques allow us to go beyond the average-case setting to the smoothed analysis setting, giving an efficient algorithm for graph isomorphism for randomly perturbed deterministic graphs under mild conditions.

Prior work by Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when $n p_n = \omega( \log^{4}(n) / \log \log n )$ (and $p_{n} \leq 1/2$); subsequently, Mossel and Ross showed that the same holds when $n p_n = \omega( \log^{2}(n) )$. We first show that their analysis essentially cannot be improved: we prove that when $n p_n = o( \log^{2}(n) / (\log \log n)^{3} )$, with high probability there exist distinct vertices with isomorphic 2-neighborhoods. Our first main result is a positive counterpart to this, showing that 3-neighborhoods give a canonical labeling when $n p_n \geq (1+\delta) \log n$ (and $p_n \leq 1/2$); this improves a recent result of Ding, Ma, Wu, and Xu, completing the picture above the connectivity threshold.

Our second main result is a smoothed analysis of graph isomorphism, showing that for a large class of deterministic graphs, a small random perturbation ensures that 3-neighborhoods give a canonical labeling with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity.

Joint work with Miklos Racz and Anirudh Sridhar.