東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Polynomial Proof Systems, Effective ...

Weitz, Benjamin.

Linked to FindBook

Google Book

Amazon

博客來

Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy./
Author:	Weitz, Benjamin.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
Description:	87 p.
Notes:	Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
Contained By:	Dissertation Abstracts International78-11B(E).
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10281364
ISBN:	9780355033571

Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.
Weitz, Benjamin.

Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 87 p.

Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.

Thesis (Ph.D.)--University of California, Berkeley, 2017.

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!

ISBN: 9780355033571Subjects--Topical Terms:

523869
Computer science.

Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.
LDR:03201nmm a2200337 4500 001 2156406
005 20180517112610.5
008 190424s2017 ||||||||||||||||| ||eng d
020 $a 9780355033571
035 $a (MiAaPQ)AAI10281364
035 $a (MiAaPQ)berkeley:16929
035 $a AAI10281364
040 $a MiAaPQ $c MiAaPQ
100 1 $a Weitz, Benjamin. $3 3344171
245 1 0 $a Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 87 p.
500 $a Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
500 $a Adviser: Prasad Raghavendra.
502 $a Thesis (Ph.D.)--University of California, Berkeley, 2017.
520 $a 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!
520 $a 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].
520 $a 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].
520 $a 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.
590 $a School code: 0028.
650 4 $a Computer science. $3 523869
650 4 $a Theoretical mathematics. $3 3173530
690 $a 0984
690 $a 0642
710 2 $a University of California, Berkeley. $b Computer Science. $3 1043689
773 0 $t Dissertation Abstracts International $g 78-11B(E).
790 $a 0028
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10281364