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 -vertex graphs and such that any sum-of-squares (SOS) proof of nonisomorphism requires degree . In other words, we show an -round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs and which are not even -isomorphic. (Here we say that two -vertex, -edge graphs and are -isomorphic if there is a bijection between their vertices which preserves at least 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 , there is no efficient algorithm which can distinguish graph pairs which are -isomorphic from pairs which are not even -isomorphic for some universal constant . Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.