We study the algorithmic problem of finding a large independent set in an Erdős–Rényi random graph $G(n,p)$. For constant $p$ and $b=1/(1-p)$, the largest independent set has size $2\log_b n$, while a simple greedy algorithm -- where vertices are revealed sequentially and the decision at any step depends only on previously seen vertices -- finds an independent set of size $\log_b n$. In his seminal 1976 paper, Karp challenged to either improve this guarantee or establish its hardness. Decades later, this problem remains one of the most prominent algorithmic problems in the theory of random graphs.

In this talk we provide some evidence for the algorithmic hardness of Karp's problem. More concretely, we establish that a broad class of online algorithms, which we shall define, fails to find an independent set of size $(1+\epsilon)\log_b n$ for any constant $\epsilon>0$, with high probability. This class includes Karp’s algorithm as a special case, and extends it by allowing the algorithm to also query additional `exceptional' edges not yet `seen' by the algorithm. For constant~$p$ we also prove that our result is asymptotically tight with respect to the number of exceptional edges queried, by  designing an online algorithm which beats the half-optimality threshold when the number of exceptional edges is slightly larger than our bound.

Our proof relies on a refined analysis of the geometric structure of tuples of large independent sets, establishing a variant of the Overlap Gap Property (OGP) commonly used as a barrier for classes of algorithms. While OGP has predominantly served as a barrier to stable algorithms, online algorithms are not stable, i.e., our application of OGP-based techniques to the online setting is novel.

Based on joint work with D. Gamarnik and E. Kızıldağ; see arXiv:2504.11450.