Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs.

Ryan O'Donnell John Wright Chenggang Wu Yuan Zhou

Published in: CoRR (2014)

Keyphrases

random graphs
graph isomorphism
phase transition
stable set
graph theoretic
semidefinite
computational complexity
image segmentation
pairwise
search space
special case
probability distribution
np complete