Midwest Theory Day

The 66th Midwest Theory Day will take place at
The University of Michigan on Saturday, December 6, 2014.

Speaker: David Steurer, Cornell University.

Title: Lower bounds on the size of semidefinite programming relaxations

Abstract: We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^{\delta}}$, for some constant $\delta > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit polytope. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX 3-SAT. Joint work with James Lee and Prasad Raghavendra.

Bio: David Steurer is an Assistant Professor at Cornell University. He investigates the power and limitations of efficient algorithms for optimization problems. A focus of his work has been semidefinite programming--the systematic combination of linear programming and spectral methods--which for a wide range of problems gives the best known and potentially optimal guarantees in terms of approximation quality. Steurer received his PhD from Princeton University and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University. He is the recipient of the 2010 FOCS best paper award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, and a Microsoft Research Faculty Fellowship.