Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

DOI10.1137/1.9781611973402.120zbMath1422.68089arXiv1401.2436OpenAlexW2951843400MaRDI QIDQ5384082

No author found.

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

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

Related Items (13)

Detecting almost symmetries of graphs ⋮ Correlated randomly growing graphs ⋮ Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ The QAP-polytope and the graph isomorphism problem ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Quantum and non-signalling graph isomorphisms ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ Spectrally Robust Graph Isomorphism ⋮ Graph Similarity and Approximate Isomorphism ⋮ A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation ⋮ Unnamed Item ⋮ The Complexity of Homomorphism Indistinguishability

This page was built for publication: Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs