The SDP value of random 2CSPs

Amulya Musipatla, Ryan O'Donnell, Tselil Schramm +1

We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~$\{\pm 1{\}}^n$. For each model $\mathcal{M}$, we identify…