Low-degree hardness of finding the largest clique in Erdős–Rényi graph (problems 36-38)

The problem of finding the largest clique in an Erdős–Rényi random graph $G(n, 1/2)$ has a special place in the study of average-case algorithmic complexity. It is one of the well-known examples of a so-called statistical-to-computational gap, a discrepancy between what is theoretically possible to achieve with unbounded computational resources and what is achievable by efficient, polynomial-time algorithms.

In a $G(n, 1/2)$, size of the maximum clique is well understood: with high probability, the largest clique has size of approximately $2 \log_2 n$. From a computational perspective, however, the best known algorithm finds a clique of size $\log_2 n$ with high probability. Perhaps surprisingly, the algorithm is a very simple greedy approach introduced by Grimmett and McDiarmid in 1975 (Grimmett & McDiarmid, 1975). It starts with an arbitrary vertex and iteratively increases the intermediate clique by adding a vertex that is connected to all vertices already in the clique until there are no such vertices left. From the implementation point of view, we can keep a list of the candidate vertices and update it after each iteration by removing all vertices not connected to a vertex added to the clique. After each step, the candidate set shrinks by a factor of two since all edges are sampled independently with probability $1/2$. Thus, the procedure halts after approximately $\log_2 n$ iterations producing a clique of the same size. This algorithm leaves a gap of $\log_2 n$ and despite decades of research, we still do not know of a polynomial-time algorithm that can do significantly better.

Does this gap stem from fundamental algorithmic limits of or from our lack of ingenuity of a better algorithm? In traditional worst-case complexity, the Clique problem is one of the foundational problems: it is one of Karp’s original NP-complete problems dating back to 1972, but also NP-hard to even approximate within a factor of $n^{1-\varepsilon}$ (Håstad, 1999).

However, worst-case lower bounds often rely on constructing a pathological example, an intricate structure designed specifically for algorithmic hardness. However, in many modern applications, the noise is not an omniscient adversary but rather an unstructured randomness. For this reason, we want to study whether a “typical” instance of a problem is hard, or in other words, if a problem can be solved with high probability. To address the average-case setting, several frameworks have emerged to provide evidence and predictions for the algorithmic lower bounds. These include the Sum-of-Squares (SoS) hierarchy, low-degree polynomials, and methods derived from statistical physics, to name just a few.

Finding a clique in $G(n,1/2)$ is a random optimization problem, where we try to maximize the size of the structured object. However, it is not rare that a planted version of the problem is easier to analyze in terms of computational complexity. In our example, instead of trying to search for a naturally occurring clique, we “plant” a much larger clique of size $k$ into an otherwise random graph. Planting a clique means choosing $k$ vertices (uniformly at random) and adding all missing edges to form a clique. By introducing this hidden ground-truth signal, we can study not only optimization (searching for a planted clique), but also detection problem (given an observed graph, can we distinguish if there is a planted clique or not?).

Because the largest clique in the unplanted model $G(n, 1/2)$ is of size approximately $2\log_2 n$, a planted clique must be strictly larger than this; otherwise, it is information-theoretically impossible to differentiate the planted clique from naturally occurring ones. We refer to this transition as the statistical threshold, which corresponds to the regime where it is possible to find the clique given unbounded computational resources. For polynomial-time algorithms, a series of works (Kučera, 1995; Alon et al., 1998; Feige & Krauthgamer, 2000) developed polynomial-time algorithms that can efficiently recover cliques of size $\Omega(\sqrt{n})$. However, despite extensive research of the problem, no polynomial-time algorithm has been found that can recover a clique of size $O(n^{1/2-\varepsilon})$ for any $\varepsilon > 0$.

This algorithmic barrier is supported by lower bounds established by numerous frameworks for average-case complexity. As it has been shown in (Barak et al., 2019; Meka et al., 2015), the SoS hierarchy requires degree $\tilde{\Omega}(\log n)$ to solve Planted Clique for $k\ll \sqrt{n}$, which implies that SDP-based approaches of this class of algorithms require super-polynomial time to break $\sqrt{n}$ threshold. In (Gamarnik & Zadik, 2024), the authors show the phase transition for the presence of the Overlap Gap Property at $k = \Theta(\sqrt{n})$ which is also known to suggest algorithmic hardness for certain classes of algorithms. Finally, the low-degree polynomials framework also adds its evidence by recovering the $k \sim \sqrt{n}$ threshold (Hopkins, 2018). Let us take a brief detour to this framework to motivate this model of computation.

Low-degree polynomial framework

The low-degree polynomial framework arose as a heuristic from the pseudo-calibration approach for proving SoS lower bounds and has since developed into an independent technique for predicting algorithmic lower bounds in high-dimensional statistical inference problems. Although the framework was initially designed for detection task between null distribution and planted model, it has since evolved for broader use cases, such as estimation and hypothesis testing between two distinct planted distributions (Schramm & Wein, 2022; Rush et al., 2022). Here a “null distribution” refers to observations drawn from pure, well-behaved, unstructured noise. Conversely, a “planted model” refers to a scenario where a hidden, structured signal is deliberately embedded, or “planted”, into that random noise.

Low-degree polynomials framework relies on analysis of the asymptotic behaviour of the so-called low-degree likelihood ratio, also referred to as low-degree advantage. For two distributions $\mathbb P$ and $\mathbb Q$ on $\mathbb R^n$, it is defined as follows.

\[\operatorname{Adv}^{\le D}_n = \max_{f: \text{$D$-deg polynomial}} \frac{\mathbb E_{\mathbb P} f - \mathbb E_{\mathbb Q} f}{\sqrt{\operatorname{Var}_{\mathbb Q} f}}.\]

Informally speaking, the above maximization seeks a low-degree polynomial that best distinguishes $\mathbb P$ and $\mathbb Q$ in the $L_2$ sense.

Low-degree polynomials capture many popular state-of-the-art approaches, including spectral methods, AMP-based algorithms, and statistical queries (Montanari & Wein, 2022; Brennan et al., 2020). There have been many “success stories” where the computational bounds predicted by low-degree polynomials precisely matched the thresholds of the best-known algorithms. While not providing formal evidence, these successes made a highly compelling case for the famous low-degree conjecture proposed by Samuel Hopkins in his thesis (Hopkins, 2018). Informally, the conjecture states that low-degree polynomials serve as a proxy for the computational power of all polynomial time algorithms for ‘natural’ statistical problems.

The crux of the matter, then, is formally defining a ‘natural’ statistical problem. Hopkins proposed the following formalization in his thesis:

Informal Conjecture (Hopkins, 2018)

Let $k\in \mathbb N$ and $\Omega$ be a finite set or $\mathbb R$. Let $\mathbb Q_n$ be a uniform distribution on $\Omega^{\binom{n}{k}}$. Let $\mathbb P_n$ be a distribution on $\Omega^{\binom{n}{k}}$ that is $S_n$-invariant (invariant under the natural relabeling). If the low-degree likelihood ratio (LDLR) for $D = (\log n)^{1+\Omega(1)}$ remains bounded as $n\to\infty$, then for every $\varepsilon > 0$ there is no $n^{D/ \operatorname{polylog} n}$-time algorithm that distinguishes between a sample from $T_{\varepsilon} \mathbb P_n$ and $\mathbb Q_n$, where $T_{\varepsilon} \mathbb P_n$ is a noisy version of $\mathbb P_n$.

Still, establishing the exact boundaries of this framework has turned out to be very subtle. Holmgren and Wein (Holmgren & Wein, 2020) first refuted the conjecture for real-valued variables, though they proposed a modified continuous noise model to patch the gap. More recently, the core Boolean version of the conjecture was also disproved by Buhai et al. (Buhai et al., 2025).

Despite this sequence of refutations, recent work (Hsieh et al., 2026) partially salvages the low-degree framework by demonstrating rigorous implications of low-degree hardness in the vector and matrix cases (i.e., when $k=1$ and $k=2$ in the setting of the conjecture above). In particular, they show that when a distribution $\mathbb P_n$ over $\mathbb R^n$ is low-degree indistinguishable from $\mathcal{N} (0, I_n)$ for some $D \ge C \log_2 n$, it implies that no statistic based on symmetric polynomials of degree up to $O(\log n / \log\log n)$ can distinguish between $\mathbb P_n$ and $\mathcal{N} (0, I_n)$. They establish a similar result for the matrix case.

The past successes of the framework, coupled with these new results regarding its implications, bring us to a fundamental open question concerning the appropriate scope of the low-degree framework.

Open Problem 35

What are the conditions on the distributions $\mathbb P_n$ and $\mathbb Q_n$ such that if the low-degree advantage remains bounded for $D = (\log n)^{1+\Omega(1)}$ as $n\to\infty$, it rigorously implies that no polynomials of a certain degree can distinguish between $\mathbb P_n$ and $\mathbb Q_n$?”

Unplanted setting

While in detection and estimation problems, we use variants of low-degree advantage to predict low-degree hardness, ruling out this class of algorithms in unplanted models lacks a concretely formulated criterion. One existing technique involves proving certain geometric properties of landscape, namely, variants of overlap gap property which implies failure of stable algorithms in a certain sense. This rules out low-degree polynomials since they exhibit some form of stability when suitably defined for the problem at hand. In this way, for unplanted clique in $G(n, 1/2)$, OGP predicts failure of low-degree polynomials of degree $o((\log n)^2)$ for cliques bigger than $\log_2 n$ (Wein, 2022).

The approach of using OGP for ruling out low-degree polynomials has a caveat that stability is not the only obstruction to failure of low-degree polynomials. This motivates searching for a technique to rule out this class of algorithms in the absence of OGP. In the example of largest clique in $G(n,1/2)$, it is known that OGP disappears for cliques of size less than $\log_2 n$. However, one may expect that constant-degree polynomials still fail to find a clique of size $\log_2 n$. There are several ways to formulate this question, and the following formulation was posed and discussed at the AIM workshop on Low-degree polynomial methods in average-case complexity in 2024.

Conjecture 35

Let $G \sim G(n, 1/2)$ and $\varepsilon > 0$. For all polynomial functions $f:{0,1}^{n \choose 2} \to \mathbb R^n$ of degree $o(\log n)$

\[\mathbb E \max_{S: k\text{-clique in } G} \langle 1_S, f \rangle \le C \cdot \mathbb E \max_{\substack{S: |E(S)| \le (1 - \varepsilon) {k \choose 2} ,\\ |S|=k}}\langle 1_S, f \rangle,\]

where $0 < C < 1$ is a constant.

On the other side, OGP predicts only a lower bound for $o(\log^2 n)$-degree polynomials, but we lack a matching upper bound. While there exists a polynomial-time algorithm for finding a clique of size $\log_2 n$, it is not clear if it can be written as a polynomial of degree $O(\log n)$ or there can be found an equivalent polynomial with similar performance for finding a clique.

Open Problem 35

Find a multivariate polynomial $f:{0,1}^{n \choose 2} \to \mathbb R^n$ of degree $O(\log n)$ such that it finds a clique of size $\log_2 n$ and has a similar structure to Definition 1.1 of (Wein, 2022) (informally, the polynomial should output a value $\ge 1$ to indicate a vertex is in a clique, $\le 1/2$ to indicate a vertex is not in a clique, and it is allowed to make small number of mistakes, that are either vertices with value $\ge 1$ violating clique constrains or vertices with value in range $(1/2,1)$)

A recent survey (Wein, 2025) highlights this gap between low-degree upper and lower bounds for other problems as well such as planted clique problem or sparse PCA. It is entirely possible that not all best-known algorithms matching the computational transition can be directly translated as polynomials, however, an interesting question remains: can we always find a low-degree polynomial with equivalent performance? Establishing these low-degree upper bounds would add credibility to the belief that low-degree polynomials serve as a universal proxy for all polynomial-time algorithms.

References

1. Grimmett, G. R., & McDiarmid, C. J. H. (1975). On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77(2), 313–324.
2. Håstad, J. (1999). Clique is hard to approximate within n 1- \varepsilon.
3. Kučera, L. (1995). Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3), 193–212.
4. Alon, N., Krivelevich, M., & Sudakov, B. (1998). Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4), 457–466.
5. Feige, U., & Krauthgamer, R. (2000). Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms, 16(2), 195–208.
6. Barak, B., Hopkins, S., Kelner, J., Kothari, P. K., Moitra, A., & Potechin, A. (2019). A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2), 687–735.
7. Meka, R., Potechin, A., & Wigderson, A. (2015). Sum-of-squares lower bounds for planted clique. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 87–96.
8. Gamarnik, D., & Zadik, I. (2024). The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. The Annals of Applied Probability, 34(4), 3375–3434.
9. Hopkins, S. (2018). Statistical Inference and the Sum of Squares Method [PhD thesis]. Cornell University.
10. Schramm, T., & Wein, A. S. (2022). Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3), 1833–1858.
11. Rush, C., Skerman, F., Wein, A. S., & Yang, D. (2022). Is it easier to count communities than find them? ArXiv Preprint ArXiv:2212.10872.
12. Montanari, A., & Wein, A. S. (2022). Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. ArXiv Preprint ArXiv:2212.06996.
13. Brennan, M., Bresler, G., Hopkins, S. B., Li, J., & Schramm, T. (2020). Statistical query algorithms and low-degree tests are almost equivalent. ArXiv Preprint ArXiv:2009.06107.
14. Holmgren, J., & Wein, A. S. (2020). Counterexamples to the low-degree conjecture. ArXiv Preprint ArXiv:2004.08454.
15. Buhai, R.-D., Hsieh, J.-T., Jain, A., & Kothari, P. K. (2025). The quasi-polynomial low-degree conjecture is false. ArXiv Preprint ArXiv:2505.17360.
16. Hsieh, J.-T., Kane, D. M., Kothari, P. K., Li, J., Mohanty, S., & Tiegel, S. (2026). Rigorous Implications of the Low-Degree Heuristic. ArXiv Preprint ArXiv:2601.05850.
17. Wein, A. S. (2022). Optimal low-degree hardness of maximum independent set. Mathematical Statistics and Learning, 4(3), 221–251.
18. Wein, A. S. (2025). Computational complexity of statistics: New insights from low-degree polynomials. ArXiv Preprint ArXiv:2506.10748.