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

preprint2014arXivOpen access

Abstract

Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic nn-vertex graphs GG and HH such that any sum-of-squares (SOS) proof of nonisomorphism requires degree Ω(n)Ω(n). In other words, we show an Ω(n)Ω(n)-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs GG and HH which are not even (1−10−14)(1-10^{-14})-isomorphic. (Here we say that two nn-vertex, mm-edge graphs GG and HH are αα-isomorphic if there is a bijection between their vertices which preserves at least αmαm edges.) Our second result is that under the {\sc R3XOR} Hypothesis \cite{Fei02} (and also any of a class of hypotheses which generalize the {\sc R3XOR} Hypothesis), the \emph{robust} Graph Isomorphism problem is hard. I.e.\ for every ε>0ε> 0, there is no efficient algorithm which can distinguish graph pairs which are (1−ε)(1-ε)-isomorphic from pairs which are not even (1−ε0)(1-ε_0)-isomorphic for some universal constant ε0ε_0. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

Explore this paper’s authors, topics and related work.

Building this map preview

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

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.