Building on work of Cai, F\"urer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic $n$-vertex graphs $G$ and $H$ such that any sum-of-squares (SOS) proof of nonisomorphism requires degree $\Omega(n)$. In other words, we show an $\Omega(n)$-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs $G$ and $H$ which are not even $(1-10^{-14})$-isomorphic. (Here we say that two $n$-vertex, $m$-edge graphs $G$ and $H$ are $\alpha$-isomorphic if there is a bijection between their vertices which preserves at least $\alpha 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 $\epsilon > 0$, there is no efficient algorithm which can distinguish graph pairs which are $(1-\epsilon)$-isomorphic from pairs which are not even $(1-\epsilon_0)$-isomorphic for some universal constant $\epsilon_0$. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok