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

Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Building on work of Cai, Fiirer, and Immerman [18], 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 nonisomor- phism requires degree Ω(n). In other words, we show an Ω (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 a-isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I.e. for every ε > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 - ε) isomorphic from pairs which are not even (1 - ε0)-)- isomorphic for some universal constant ε0)- Along the way we prove a robust asymmetry result for random graphs and hyper- graphs which may be of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery,
Pages1659-1677
Number of pages19
ISBN (Print)9781611973389
StatePublished - Jan 1 2014
Externally publishedYes
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR
Period1/5/141/7/14

Fingerprint

Graph Isomorphism
Random Graphs
Hardness
Asymmetry
Isomorphic
Graph in graph theory
Isomorphism Problem
Integrality
Sum of squares
Vertex of a graph
Bijection
Hypergraph
Efficient Algorithms
Generalise

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

O'Donnell, R., Wright, J., Wu, C., & Zhou, Y. (2014). Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 (pp. 1659-1677). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery,.

Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. / O'Donnell, Ryan; Wright, John; Wu, Chenggang; Zhou, Yuan.

Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. p. 1659-1677 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

O'Donnell, R, Wright, J, Wu, C & Zhou, Y 2014, Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1659-1677, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14.
O'Donnell R, Wright J, Wu C, Zhou Y. Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery,. 2014. p. 1659-1677. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
O'Donnell, Ryan ; Wright, John ; Wu, Chenggang ; Zhou, Yuan. / Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. pp. 1659-1677 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{735dc9ace2a34d829967b8656136f18a,
title = "Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs",
abstract = "Building on work of Cai, Fiirer, and Immerman [18], 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 nonisomor- phism requires degree Ω(n). In other words, we show an Ω (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 a-isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I.e. for every ε > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 - ε) isomorphic from pairs which are not even (1 - ε0)-)- isomorphic for some universal constant ε0)- Along the way we prove a robust asymmetry result for random graphs and hyper- graphs which may be of independent interest.",
author = "Ryan O'Donnell and John Wright and Chenggang Wu and Yuan Zhou",
year = "2014",
month = "1",
day = "1",
language = "English (US)",
isbn = "9781611973389",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery,",
pages = "1659--1677",
booktitle = "Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014",

}

TY - GEN

T1 - Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs

AU - O'Donnell, Ryan

AU - Wright, John

AU - Wu, Chenggang

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Building on work of Cai, Fiirer, and Immerman [18], 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 nonisomor- phism requires degree Ω(n). In other words, we show an Ω (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 a-isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I.e. for every ε > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 - ε) isomorphic from pairs which are not even (1 - ε0)-)- isomorphic for some universal constant ε0)- Along the way we prove a robust asymmetry result for random graphs and hyper- graphs which may be of independent interest.

AB - Building on work of Cai, Fiirer, and Immerman [18], 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 nonisomor- phism requires degree Ω(n). In other words, we show an Ω (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 a-isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I.e. for every ε > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 - ε) isomorphic from pairs which are not even (1 - ε0)-)- isomorphic for some universal constant ε0)- Along the way we prove a robust asymmetry result for random graphs and hyper- graphs which may be of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=84902089891&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902089891&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84902089891

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1659

EP - 1677

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery,

ER -