David Witmer - CMU

Monday, December 5, 2016

Klaus 1116 East - 11:00 am

Title:
Using the sum of squares hierarchy to refute random CSPs

Abstract:
Consider a random constraint satisfaction problem (CSP) over $n$ variables with $m = Δ n$ constraints, each being a predicate $P$ applied to $k$ random literals. When Δ >> 1$, 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 discuss refutation of random CSPs using the sum of squares (SOS) hierarchy.  The SOS hierarchy is a sequence of semidefinite relaxations parameterized by a value called the degree.  As the degree increases, the relaxation becomes tighter, but the size of its description increases.  We give an overview of recent work proving that the SOS degree required to refute a random instance of CSP$(P)$ is essentially determined by the smallest $t$ for which $P$ does not support a $t$-wise uniform distribution over satisfying assignments.  Specifically, if $P$ fails to support a $t$-wise uniform distribution, our work together with recent work of Raghavendra, Rao, and Schramm shows that degree-$\frac{n}{\Delta^{2/(t-2)}}$ SOS can refute random instances of CSP$(P)$.  Furthermore, this result is tight up to polylogarithmic factors.

This talk is based on joint work with Sarah R. Allen, Pravesh Kothari, Ryuhei Mori, and Ryan O’Donnell.

URL: http://www.cs.cmu.edu/~dwitmer/

Seminar webpage: http://arc.gatech.edu/hg/item/582448

Fall 2016 ARC Seminar Schedule