*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
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
