Lower bounds for CSP refutation by SDP hierarchies

Ryuhei Mori, David Witmer

For a $k$-ary predicate $P$, a random instance of CSP$(P)$ with $n$ variables and $m$ constraints is unsatisfiable with high probability when $m\gg n$. The natural algorithmic tas…