David Witmer

Refutation of random constraint satisfaction problems using the sum of squares proof system Degree Type: Ph.D. in Computer Science
Advisor(s): Anupam Gupta, Ryan O'Donnell
Graduated: May 2017

Abstract:

Given a k-ary predicate P, a random instance of a constraint satisfaction problem with predicate P (CSP(P)) is a set of m constraints on n variables. Each constraint is P applied to k random literals. Such an instance is unsatisfiable with high probability when m ≫ n. Although this fact can be proven via a simple probabilistic argument, certifying that a given randomly chosen instance is unsatisfiable, a task called refutation, remains a challenge. Refutation, besides being a natural problem in its own right, has applications in cryptography, hardness of approximation, and learning theory. This thesis studies refutation using sum-of-squares (SOS) proof systems [GV01]. SOS is a sequence of increasingly powerful methods for proving polynomial inequalities parameterized by a value called the degree: the higher the degree, the more powerful the proof system. On the other hand, the amount of computation needed to find an SOS proof increases with degree: a degree-d proof can be found in time n^O(d) [Sho87, Par00, Las00, Las01].

First, we consider refutation via constant-degree SOS proofs, which can be found in polynomial time. We show that the number of constraints required for constant degree SOS refutation of a random instance of CSP(P) is determined by a complexity parameter C(P), the minimum t for which there is no t-wise uniform distribution over {0, 1} supported on satisfying assignments to P. With Allen and O'Donnell [AOW15], we proved that constant-degree SOS can refute a random instance of CSP(P) when m = Õ (n^C(P)/2). With Kothari, Mori, and O'Donnell [KMOW17], we showed a nearly matching lower bound: SOS requires superconstant degree to refute random instances of CSP(P) when m = Ω^̃(n^C(P)/2).

More generally, we consider the stronger notion of -refutation, certifying that at most a 1-δ fraction of constraints can be simultaneously satisfied. We also consider SOS proofs with arbitrary, possibly superconstant, degree. In [AOW15], we proved that if every t-wise uniform distribution on {0, 1}^K is δ-far from every distribution supported on satisfying assignments to P, then constant-degree SOS can (δ - o(1))-refute a random instance of CSP(P) with m = Õ(n^C(P)/2)). For such P, this can be extended using a result of Raghavendra, Rao, and Schramm [RRS17] to obtain (δ - o(1))-refutation of random instances of CSP(P) with m = Δn constraints via degree-Õ(n/Δ^2/(t-2)) SOS. In [KMOW17], we proved that (δ + o(1))-refutation of a random instance of CSP(P) with m = Δn constraints requires SOS degree Ω^̃(n/Δ^2/(t-1)) when there exists a t-wise uniform distribution that is δ-close to being supported on satisfying assignments to P. These results establish a three-way trade-off among number of constraints, SOS degree, and refutation strength δ that is tight up to logarithmic factors.

Thesis Committee:
Anupam Gupta (Co-Chair)
Ryan O'Donnell (Co-Chair)
Alan Frieze
Boaz Barak (Harvard University)
Eli Ben-Sasson (Technion-Israel Institute of Technology)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Constraint satisfaction problems, average-case complexity, semidenite programming, proof complexity