For More Information:

deb@cs.cmu.edu
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. Refutation is certifying that a given randomly chosen instance is unsatisfiable. This task has applications in cryptography, hardness of approximation, and learning theory. This thesis studies refutation using sum-of-squares (SOS) proof systems. SOS is a sequence of increasingly powerful proof systems parameterized by degree: the higher the degree, the more powerful the proof system. On the other hand, finding an SOS proof requires time exponential in the degree. 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 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}^k supported on satisfying assignments to P. With Allen and O'Donnell, we proved that constant-degree SOS can refute CSP(P) when m = O~(n^{C(P)/2}). With Kothari, Mori, and O'Donnell, we showed a nearly matching lower bound. More generally, we consider delta-refutation, certifying that at most a 1-delta fraction of constraints can be simultaneously satisfied. We also consider SOS proofs with arbitrary, possibly superconstant, degree. With Allen and O’Donnell, we showed that if every t-wise uniform distribution is delta-far from every distribution supported on satisfying assignments to P, then constant-degree SOS can (delta-o(1))-refute CSP(P) with m = O~(n^{t/2}). For such P, this can be extended using a result of Raghavendra, Rao, and Schramm to obtain (delta-o(1))-refutation with m = \Delta n constraints via degree-O~(n/Delta^{2/(t-2)}) SOS. With Kothari, Mori, and O’Donnell, we proved that (delta+o(1))-refutation of CSP(P) with Delta n constraints requires SOS degree Omega~(n/Delta^{2/(t-1)}) when there exists a t-wise uniform distribution that is delta-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 delta 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)

Event Categories:

Thesis Oral