Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs

October 16, 2013

Given two graphs which are almost isomorphic, is it possible to find a bijection which preserves most of the edges between the two? This is the algorithmic task of Robust Graph Isomorphism, which is a natural approximation variation of the Graph Isomorphism problem. In this talk, we show that no polynomial-time algorithm solves this problem, conditioned on Feige's Random 3XOR Hypothesis. In addition, we show that the Lasserre/SOS SDP hierarchy, the most powerful SDP hierarchy known, fails quite spectacularly on this problem: it needs a linear number of rounds to distinguish two isomorphic graphs from two far-from-isomorphic graphs. Along the way, we venture into the theory of random graphs by showing that a random graph is robustly asymmetric whp, meaning that any permutation which is close to an automorphism is itself close to the identity permutation.

*This is joint work with Ryan O'Donnell, Chenggang Wu, and Yuan Zhou*