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

Ryan O'Donnell John Wright Chenggang Wu Yuan Zhou

Published in: SODA (2014)

Keyphrases

random graphs
graph isomorphism
phase transition
stable set
semidefinite
graph theoretic
small world
search algorithm
computational complexity
state space
supervised learning
ranking algorithm
satisfiability problem
graph mining