The AIM low-degree conjecture for independent sets in dense random graphs

Let $G(n,\frac12)$ be the Erdős–Rényi random graph with edge probability $\frac12$. A low-degree polynomial is a polynomial in the input encoding of the graph whose degree measures its computational complexity.

AIM low-degree conjecture. In $G(n,\frac12)$, no degree-$o(\log^2 n)$ polynomial can find an independent set of size $0.9\log_2 n$.

This conjecture asserts a low-degree barrier even in the algorithmically easy regime for the maximum independent set problem. Its resolution would clarify whether low-degree polynomials capture the limitations of natural algorithms in dense random graphs.