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

Ryan O'Donnell, John Wright, Chenggang Wu +1

Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic $n$-…