The Taub Faculty of Computer Science Events and Talks

Consider a random constraint satisfaction problem (CSP) over $n$ variables with $m$ constraints, each being a predicate $P$ applied to $k$ random literals. When $m \gg n$ the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability. Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.

In this talk, we give a general criterion that often allows efficient refutation at much lower densities than previous algorithms. Specifically, if $P$ fails to support a $t$-wise uniform probability distribution, then there is an efficient algorithm that refutes random instances with high probability, provided $m \gg n^{t/2}$. Indeed, our algorithm will ``somewhat strongly'' refute instances, certifying that the optimum is bounded away from 1. If $t = k$, then we furthermore get the strongest possible refutation, certifying that the optimum is within o(1) of its expectation. This last result is new even in the context of random $k$-SAT. Our refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy and prior work on SDP hierarchies provides evidence that its dependence on $m$ is optimal for every $P$.

This is joint work with Sarah R. Allen and Ryan O’Donnell.