This site is to serve as my note-book and to effectively communicate with my students and collaborators. Every now and then, a blog may be of interest to other researchers or teachers. Views in this blog are my own. All rights of research results and findings on this blog are reserved. See also http://youtube.com/c/hongqin @hongqin
Saturday, September 29, 2018
graph permutation, isomorphism, 3xor hypothesis
3xor hypothesis
Yuan Zhou, hardness of robust graph isomorphism, Lassere gaps, and asymmetry of random graphs
https://www.youtube.com/watch?v=gAsQsEMgWU0
Given two graphs which are almost isomorphic, is it possible to find a bijection which preserves most of the edges between the two? This is the algorithmic task of Robust Graph Isomorphism, which is a natural approximation variation of the Graph Isomorphism problem. In this talk, we show that no polynomial-time algorithm solves this problem, conditioned on Feige's Random 3XOR Hypothesis. In addition, we show that the Lasserre/SOS SDP hierarchy, the most powerful SDP hierarchy known, fails quite spectacularly on this problem: it needs a linear number of rounds to distinguish two isomorphic graphs from two far-from-isomorphic graphs. Along the way, we venture into the theory of random graphs by showing that a random graph is robustly asymmetric whp, meaning that any permutation which is close to an automorphism is itself close to the identity permutation. Joint work with Ryan O'Donnell, John Wright, and Chenggang Wu.
Labels:
graph,
network permutation
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment