Title: A Nearly Tight Sum of Squares Lower Bound for Planted Clique
Speaker: Pravesh Kothari, Princeton University
Date: Wednesday, November 9, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We prove that with high probability over the draw of a graph from the Erdös-Renyi distribution G(n,1/2), the ~n^d time, degree d sum of squares relaxation for the clique problem gives a value of ~n^{1/2-o(1)} for any d = o(\log(n)). This yields a nearly tight n^{1/2-o(1)} lower-bound on the value of this program for any degree d=o(logn).
Key to the proof is a new framework that we call pseudo-calibration to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/