Is Planted Coloring Easier than Planted Clique?

We study the computational complexity of two related problems: recovering a planted q-coloring in G(n, 1/2), and finding efficiently verifiable witnesses of non-q-colorability (a.k.a. refutations) in G(n, 1/2). Our main results show hardness for both these problems in a restricted-but-powerful class of algorithms based on computing low-degree polynomials in the inputs. The problem of recovering a planted q-coloring is equivalent to recovering q disjoint planted cliques that cover all the vertices — a potentially easier variant of the well-studied planted clique problem. Our first result shows that this variant is as hard as the original planted clique problem in the low-degree polynomial model of computation: each clique needs to have size k ≫ √n for efficient recovery to be possible. For the related variant where the cliques cover a (1 − ϵ)-fraction of the vertices, we also show hardness by reduction from planted clique. Our second result shows that refuting q-colorability of G(n, 1/2) is hard in the low-degree polynomial model when q ≫ n²/³ but easy when q ≲ n¹/², and we leave closing this gap for future work. Our proof is more subtle than similar results for planted clique and involves constructing a non-standard distribution over q-colorable graphs. We note that while related to several prior works, this is the first work that explicitly formulates refutation problems in the low-degree polynomial model. The proofs of our main results involve showing low-degree hardness of hypothesis testing between an appropriately constructed pair of distributions. For refutation, we show completeness of this approach: in the low-degree model, the refutation task is precisely as hard as the hardest associated testing problem, i.e., proving hardness of refutation amounts to finding a “hard” distribution.