Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy
Benjamin Weitz
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2017-38
May 9, 2017
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-38.pdf
Semidefinite 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.
Advisors: Prasad Raghavendra
BibTeX citation:
@phdthesis{Weitz:EECS-2017-38,
Author= {Weitz, Benjamin},
Title= {Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy},
School= {EECS Department, University of California, Berkeley},
Year= {2017},
Month= {May},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-38.html},
Number= {UCB/EECS-2017-38},
Abstract= {Semidefinite 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.},
}
EndNote citation:
%0 Thesis %A Weitz, Benjamin %T Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy %I EECS Department, University of California, Berkeley %D 2017 %8 May 9 %@ UCB/EECS-2017-38 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-38.html %F Weitz:EECS-2017-38