Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random
Graphs
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random
Graphs
We prove that for every $D \in \N$, and large enough constant $d \in \N$, with high probability over the choice of $G \sim G(n,d/n)$, the \Erdos-\Renyi random graph distribution, the canonical degree $2D$ Sum-of-Squares relaxation fails to certify that the largest independent set in $G$ is of size $o(\frac{n}{\sqrt{d} …