Abstract
We will discuss the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We will describe evidence for 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. These results are better described in the more general problem of certifying an upper bound on the maximum k-cut.
This quiet planting is achieved by minimizing the effect of the planted structure (e.g. colorings or cuts) on the graph spectrum. Specifically, the planted structure corresponds exactly to eigenvectors of the adjacency matrix. This avoids the pushout effect of random matrix theory, and delays the point at which the planting becomes visible in the spectrum or local statistics. Our evidence for computational hardness of distinguishing two distributions is based on three different heuristics: stability of belief propagation, the local statistics hierarchy, and the low-degree likelihood ratio. We will also describe some open problems time permitting. Joint work with: Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein.