Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2

We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…