Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy
- Author(s): Weitz, Benjamin
- Advisor(s): Raghavendra, Prasad
- et al.
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 .
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 , 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 .
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.