Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs

Pravesh Kothari, Aaron Potechin, Jeff Xu

We prove that for every $D\in \mathbb{N}$, and large enough constant $d\in \mathbb{N}$, with high probability over the choice of $G\sim G(n,d/n)$, the \Erdos-\Renyi random graph distribution, t…