OP-00050 Open

A low-degree polynomial that finds cliques of size log₂ n in G(n, 1/2)

Let $G \sim G(n, \frac12)$. The greedy algorithm of Grimmett and McDiarmid finds a clique of size about $\log_2 n$ in polynomial time, and the overlap gap property predicts that polynomials of degree $o((\log n)^2)$ fail to find larger cliques (Wein), but no matching low-degree upper bound is known: it is not clear whether the greedy algorithm, or anything that performs as well, can be written as a polynomial of degree $O(\log n)$.

Problem. Find a polynomial $f : \{0,1\}^{\binom n2} \to \mathbb{R}^n$ of degree $O(\log n)$ that finds a clique of size $\log_2 n$ and has a structure similar to Definition 1.1 of Wein (2022): informally, $f$ outputs a value $\ge 1$ on vertices of the clique and $\le \frac12$ on other vertices, and may make a small number of mistakes, namely vertices with value $\ge 1$ that violate the clique constraints or vertices with value in $(\frac12, 1)$.

Source: Kireeva, Open Problem 38 of Randomstrasse101, in “Low-degree hardness of finding the largest clique in Erdős–Rényi graph” (2026).

The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.

Classification

Primary: PR — Probability
Secondary: CO, ST
Keywords: clique number, low-degree polynomials, random graphs, Randomstrasse101
Literature checked: Oct. 2, 2026 by clemens-admin

References

@misc{kireeva2026clique,
  author = {Kireeva, Anastasia},
  title = {Low-degree hardness of finding the largest clique in {E}rd{\H{o}}s--{R}{\'e}nyi graph (problems 36--38)},
  howpublished = {Randomstrasse101 blog},
  year = {2026},
  url = {https://randomstrasse101.math.ethz.ch/posts/clique-low-degree/}
}

@article{wein2022independent,
  author = {Wein, Alexander S.},
  title = {Optimal low-degree hardness of maximum independent set},
  journal = {Mathematical Statistics and Learning},
  volume = {4},
  number = {3--4},
  pages = {221--251},
  year = {2022},
  doi = {10.4171/MSL/25},
  eprint = {2010.06563},
  archivePrefix = {arXiv}
}

@article{grimmett1975colouring,
  author = {Grimmett, G. R. and McDiarmid, C. J. H.},
  title = {On colouring random graphs},
  journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
  volume = {77},
  number = {2},
  pages = {313--324},
  year = {1975}
}

@misc{wein2025survey,
  author = {Wein, Alexander S.},
  title = {Computational complexity of statistics: new insights from low-degree polynomials},
  year = {2025},
  eprint = {2506.10748},
  archivePrefix = {arXiv}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00050, "A low-degree polynomial that finds cliques of size log₂ n in G(n, 1/2)", clopen.solutions.