Theory Lunch Seminar

Wednesday, November 30, 2016 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates & Hillman Centers



Let P be a k-ary predicate. Consider a random instance of the constraint satisfaction problem CSP(P) on n variables with Δn constraints, each being P applied to k randomly chosen literals. When Δ>>1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability. The sum of squares (SOS) hierarchy is a powerful algorithmic tool in the study of CSPs. It is a sequence of semidefinite programming relaxations parameterized by the degree d. The relaxation becomes tighter as d increases, but it takes nO(d) time to solve. In this talk, we will discuss a lower bound on the SOS degree required to refute a random instance of CSP(P): If P supports a t-wise-uniform probability distribution on its satisfying assignments, the SOS algorithm of degree d=Θ(n/Δ2/(t-1)) cannot refute. By recent algorithmic results, this bound is essentially tight. This is joint work with Pravesh K. Kothari, Ryuhei Mori, and Ryan O.Donnell. This is joint work with Pravesh K. Kothari, Ryuhei Mori, and Ryan O’Donnell. — David Witmer is a PhD student in the Computer Science Department at CMU. His advisors are Anupam Gupta and Ryan O'Donnell. Supported in part by Yahoo! Labs and the Simons Foundation

Event Website:

For More Information, Contact:


Seminar Series