  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.
