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
Y1 - 2014
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
U2 - 10.1137/1.9781611973402.120
DO - 10.1137/1.9781611973402.120
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
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -