Sum-of-Squares Lower Bounds for Coloring Random Graphs

In this paper, we prove Sum-of-Squares lower bounds for the coloring problem on random graphs. In particular, we show that for all є > 0, if G ∼ G(n,1/2) then with high probability, SoS requires degree Ω(logn) in order to prove that the chromatic number of G is at least n1/2 + є. Our result extends analogously for sparse random graphs from G(n,d/n) for logn ≤ d ≪ √n. Despite being a major goal in the study of integrality gaps for the Sum-of-Squares relaxation, before this work, such a result was known only for the basic -Theta SDP relaxation (equivalently, degree 2 Sum-of-Squares). While the related problem of Sum-of-Squares bounds for the independence numbers of random graphs has been progressively resolved over the past few years, similar progress on coloring requires tackling the challenge that the natural planted distribution is easily distinguishable from G(n,1/2) as well as new challenges in handling multiple exact equality constraints. In this work, we introduce new technical tools to tackle these challenges. We design a new principled “fix” to the pseudo-expectation values given by pseudo-calibration in order to address the failure of low-degree indistinguishability while still respecting the exact equality constraints. Our analysis of the new construction relies on an approximate matrix factorization technique via a new type of vertex separator which we call rainbow separators.