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

Understand

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-case computational hardness for this problem in sparse random regular graphs, showing optimality of a simple spectral certificate.
• This evidence takes the form of a computationally-quiet planting: we construct a distribution of d-regular graphs that has significantly smaller chromatic number than a typical regular graph drawn uniformly at random, while providing evidence that these two distributions are indistinguishable by a large class of algorithms.
• We generalize our results to the more general problem of certifying an upper bound on the maximum k-cut.