Dissertation Talk: Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hieararchy

Seminar | May 4 | 1-2 p.m. | 606 Soda Hall

 Benjamin Weitz, Berkeley EECS

 Electrical Engineering and Computer Sciences (EECS)

The Sum-of-Squares (SOS) SDP Hierarchy has recently emerged as a powerful tool for approximation algorithms, tensor recovery problems, and more. Because it is relatively new, we still do not know the answer to even very basic questions about the hierarchy. For example, we do not even know when the SOS SDP is guaranteed to run correctly in polynomial time! We would also like to know when the SOS SDP performs well, specifically when achieves the same approximation as any other SDP of a comparable size.

In this talk we make progress on both of these questions, giving a sufficient, checkable criteria for when an SOS SDP will run in polynomial time, as well as proving that no symmetric SDP performs better than SOS on the Matching and TSP problems. Our results make use of low-degree certificates of ideal membership for the polynomial ideal formed by the constraints. Thus a key step in our proofs is constructing certificates for arbitrary polynomials in the corresponding constraint ideals.

 bsweitz@eecs.berkeley.edu, 6513669337