Strongly Refuting Random CSPs Below the Spectral Threshold

Wednesday, May 25, 2016 - 4:00pm to 5:00pm
Tselil Schramm
UC Berkeley

Random instances of 3-SAT are known to be unsatisfiable with high probability when there at least 5N clauses. However, given a random 3-SAT instance on N variables, the task of refuting the instance, or of proving that the instance has no satisfying assignments, is hypothesized to be computationally hard if there are O(N) clauses--in fact, the best known efficient algorithms for refutation require instances with at least \Omega(N^{3/2}) clauses, a factor of N^{1/2} beyond the unsatisfiability threshold at \Theta(N).

In this talk, I will describe a new spectral algorithm that refutes 3-SAT instances with fewer clauses, given more time. Specifically, our algorithm refutes instances with \Theta(N^{3/2 - \delta/2}) clauses in exp(O(N^\delta)) time, giving the same guarantees as the best known polynomial-time algorithms when \delta = 0, and from there smoothly approaching the unsatisfiability threshold at \delta = 1. Further, our algorithm strongly refutes the instances, certifying that no assignment satisfies more than a (1-\epsilon)-fraction of constraints for a constant \epsilon.

Our algorithm also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere (injective tensor norm).

Based on joint work with Prasad Raghavendra and Satish Rao.