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

DOI10.1137/1.9781611973402.120MaRDI QIDQ5384082zbMATH OpenOpenAlexFDO

Authors

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2436

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 $alpham$ 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-epsilo{n}_0)$-isomorphic for some universal constant $epsilo{n}_0$. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

Recommendations

• On the Hardness of Graph Isomorphism
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Constructing hard examples for graph isomorphism
• Graph isomorphism in quasipolynomial time (extended abstract)
• Attacks on hard instances of graph isomorphism

Cited in

(19)

• Detecting almost symmetries of graphs
• The QAP-polytope and the graph isomorphism problem
• Limitations of semidefinite programs for separable states and entangled games
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• The robustness of LWPP and WPP, with an application to graph reconstruction
• Correlated randomly growing graphs
• Quantum and non-signalling graph isomorphisms
• Limitations of algebraic approaches to graph isomorphism testing
• Spectrally robust graph isomorphism
• Graph similarity and approximate isomorphism
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• The Complexity of Homomorphism Indistinguishability
• Constructing hard examples for graph isomorphism
• scientific article; zbMATH DE number 7055493 (Why is no real title available?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Cutting planes width and the complexity of graph isomorphism refutations
• Supercritical size-width tree-like resolution trade-offs for graph isomorphism

This page was built for publication: Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384082)