## Abstract

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^{2}/^{3} but easy when q ≲ n^{1}/^{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 language | English (US) |
---|---|

Pages (from-to) | 5343-5372 |

Number of pages | 30 |

Journal | Proceedings of Machine Learning Research |

Volume | 195 |

State | Published - 2023 |

Externally published | Yes |

Event | 36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India Duration: Jul 12 2023 → Jul 15 2023 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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