English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Building on work of Cai, F\"urer, and Immerman \cite{CFI92}, we show twohardness results for the Graph Isomorphism problem. First, we show that thereare pairs of nonisomorphic $n$-vertex graphs $G$ and $H$ such that anysum-of-squares (SOS) proof of nonisomorphism requires degree $\Omega(n)$. Inother words, we show an $\Omega(n)$-round integrality gap for the Lasserre SDPrelaxation. 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 theirvertices which preserves at least $\alpha m$ edges.) Our second result is thatunder the {\sc R3XOR} Hypothesis \cite{Fei02} (and also any of a class ofhypotheses which generalize the {\sc R3XOR} Hypothesis), the \emph{robust}Graph Isomorphism problem is hard. I.e.\ for every $\epsilon > 0$, there is noefficient 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 theway we prove a robust asymmetry result for random graphs and hypergraphs whichmay be of independent interest.

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