國立虎尾科技大學 |

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

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy./
Author:	Weitz, Benjamin.
Description:	1 online resource (87 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
Contained By:	Dissertation Abstracts International78-11B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
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. - 1 online resource (87 pages)

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

Thesis (Ph.D.)

Includes bibliographical references

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!

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355033571Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.
LDR:03538ntm a2200385Ki 4500 001 910767
005 20180517112610.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355033571
035 $a (MiAaPQ)AAI10281364
035 $a (MiAaPQ)berkeley:16929
035 $a AAI10281364
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Weitz, Benjamin. $3 1182221
245 1 0 $a Polynomial Proof Systems, Effective Derivations, and Their Applications in the Sum-of-Squares Hierarchy.
264 0 $c 2017
300 $a 1 online resource (87 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
500 $a Adviser: Prasad Raghavendra.
502 $a Thesis (Ph.D.) $c University of California, Berkeley $d 2017.
504 $a Includes bibliographical references
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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Theoretical mathematics. $3 1180455
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0642
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Berkeley. $b Computer Science. $3 1179511
773 0 $t Dissertation Abstracts International $g 78-11B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10281364 $z click for full text (PQDT)