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 task in this regime is \emph{ refutation}: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP$(P)$ using an SDP is determined by a parameter $\mathrm{ cmplx}(P)$, the smallest $t$ for which there does not exist a $t$-wise uniform distribution over satisfying assignments to $P$. In particular they show that random instances of CSP$(P)$ with $m \gg n^{ \mathrm{ cmplx(P)}/2}$ can be refuted efficiently using an SDP. In this work, we give evidence that $n^{ \mathrm{ cmplx}(P)/2}$ constraints are also \emph{ necessary} for refutation using SDPs. Specifically, we show that if $P$ supports a $(t-1)$-wise uniform distribution over satisfying assignments, then the Sherali-Adams$_+$ and Lov\'{ a}sz-Schrijver$_+$ SDP hierarchies cannot refute a random instance of CSP$(P)$ in polynomial time for any $m \leq n^{ t/2-\epsilon}$.
Categories: cs.CC