# Is Planted Coloring Easier than Planted Clique?

arXiv: https://arxiv.org/abs/2303.00252 · HTML: https://mlsanity.com/paper/2303.00252/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2023.

## Built on by (most cited first, 7 of 7)

- [Reinforced Generation of Combinatorial Structures: Hardness of Approximation](https://mlsanity.com/paper/2509.18057/) (2025)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models](https://mlsanity.com/paper/2412.21155/) (2024)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

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 gg √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 gg n2/3 but easy when q lesssim n1/2, 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.