Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
复制标题
DOI：
10.1137/1.9781611973402.120
复制
发表时间：
2014-01
期刊：
影响因子：
--
通讯作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
中科院分区：
文献类型：
--
作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
在Cai，Furer和Immerman [18]的工作基础上，我们给出了图同构问题的两个困难结果。首先，我们证明了存在非同构的n-顶点图对G和H，使得任何非同构的平方和（SOS）证明需要度Ω（n）。换句话说，我们证明了拉瑟尔SDP松弛的O（n）轮完整性缺口。事实上，我们证明了这对G和H甚至不是（1- 10 - 14）-同构。(Here我们称两个n-点m-边图G和H是α-同构的，如果它们的顶点之间存在一个至少保持αm条边的双射。我们的第二个结果是，在R3 XOR假设[23]（以及推广R3 XOR假设的一类假设中的任何一个）下，鲁棒图同构是困难的。也就是说，对于每个e > 0，对于某个泛常数e0，没有有效的算法可以区分（1 -- e）-同构的图对和甚至不是（1 -- e0）-同构的图对。沿着的方式，我们证明了一个强大的随机图和超图，这可能是独立的利益不对称的结果。
Building on work of Cai, Furer, 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 nonisomorphism requires degree Ω(n). In other words, we show an O(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 α-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 e > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 -- e)-isomorphic from pairs which are not even (1 -- e0)-isomorphic for some universal constant e0. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.