UC Berkeley

Semidenite programming (SDP) relaxations have been a popular choice for approximation

algorithm design ever since Goemans and Williamson used one to improve the best approximation

of Max-Cut in 1992. In the effort to construct stronger and stronger SDP relaxations,

the Sum-of-Squares (SOS) or Lasserre hierarchy has emerged as the most promising

set of relaxations. However, since the SOS hierarchy is relatively new, we still do not know

the answer to even very basic questions about its power. For example, we do not even know

when the SOS SDP is guaranteed to run correctly in polynomial time!

In this dissertation, we study the SOS hierarchy and make positive progress in

understanding the above question, among others. First, we give a sufficient, simple criteria

which implies that an SOS SDP will run in polynomial time, as well as confirm that our

criteria holds for a number of common applications of the SOS SDP. We also present an

example of a Boolean polynomial system which has SOS certificates that require exponential time to find, even though the certificates are degree two. This answers a conjecture of [54].

Second, we study the power of the SOS hierarchy relative to other symmetric SDP relaxations

of comparable size. We show that in some situations, the SOS hierarchy achieves

the best possible approximation among every symmetric SDP relaxation. In particular, we

show that the SOS SDP is optimal for the Matching problem. Together with an SOS lower

bound due to Grigoriev [32], this implies that the Matching problem has no subexponential

size symmetric SDP relaxation. This can be viewed as an SDP analogy of Yannakakis'

original symmetric LP lower bound [72].

As a key technical tool, our results make use of low-degree certificates of ideal membership

for the polynomial ideal formed by polynomial constraints. Thus an important step in our

proofs is constructing certificates for arbitrary polynomials in the corresponding constraint

ideals. We develop a meta-strategy for exploiting symmetries of the underlying combinatorial

problem. We apply our strategy to get low-degree certificates for Matching, Balanced CSP, TSP, and others.