Is Planted Coloring Easier than Planted Clique?

Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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 ≫ n2/3 but easy when q ≲ 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.

Original languageEnglish (US)
Pages (from-to)5343-5372
Number of pages30
JournalProceedings of Machine Learning Research
StatePublished - 2023
Externally publishedYes
Event36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India
Duration: Jul 12 2023Jul 15 2023

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


  • coloring
  • computational complexity
  • low-degree polynomials
  • Random graphs


Dive into the research topics of 'Is Planted Coloring Easier than Planted Clique?'. Together they form a unique fingerprint.

Cite this