The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

Jess Banks, Robert Kleinberg, Cristopher Moore

We derive upper and lower bounds on the degree $d$ for which the Lovász $\vartheta$ function, or equivalently sum-of-squares proofs with degree two, can refute the existence of a $…