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

Let $\mathbb{G}(n,1/2)$ be the Erdős–Rényi random graph on $n$ vertices, and let a degree-$r$ polynomial algorithm mean a polynomial of degree at most $r$ used to find an independent set. Low-degree polynomial hardness conjecture. On $\mathbb{G}(n,1/2)$, no degree $o(\log^2 n)$ polynomial finds an independent set of size $0.9\log_2 n$. This conjecture asserts that low-degree polynomial algorithms perform substantially worse than the greedy algorithm on dense random graphs; its resolution would clarify the computational hardness of finding large independent sets in this regime.