CMU-CS-17-114 Computer Science Department School of Computer Science, Carnegie Mellon University
Refutation of random constraint satisfaction David Witmer April 2017 Ph.D. Thesis
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 constantdegree 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. 116 pages
Thesis Committee:
Frank Pfenning, Head, Computer Science Department
| |
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |