The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes

The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes

Loading...

##### Date

2018

##### Authors

##### Editors

##### Journal ISSN

##### Electronic ISSN

##### ISBN

##### Bibliographical data

##### Publisher

##### Series

##### URI (citable link)

##### International patent number

##### Link to the license

##### EU project number

##### Project

##### Open Access publication

##### Collections

##### Title in another language

##### Publication type

Dissertation

##### Publication status

Published

##### Published in

##### Abstract

In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORR

The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP.

In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORR

An elaboration of this work of [LRS] is the main part of our thesis. It is our objective and intention to present a very detailed version of their proof and in the ideal case a version that makes it easier to understand their brilliant work. In this connection, it is our motivation to bring their work to a broader number of people.

On the other hand, we present some of our own ideas by which we even obtain some slightly stronger results than [LRS] at some points. By the way, we illustrate way [LRS] could even show a stronger lower bound than they claimed in their original work.

On the whole, this thesis can be divided into three parts. The already mentioned proof of the work of [LRS] forms the second one. In the first part, we present a new and easier proof of a famous and often cited theorem of Grigoriev, where he proved lower bounds on the degree of the Real Nullstellensatz. On the one hand, Grigoriev's Theorem is on its own of high significance for questions concerning the power and complexity of algorithms relying on sums of squares and solving problems as they appear frequently in combinatorial optimization, on the other hand, this results is also essential for the work of [LRS]. We also present two applications of Grigoriev`s theorem respectively its proof.

In the last part of our thesis, we take a look on so-called pseudo-expectations and pseudo-densities, Boolean functions with specific properties, that are one of the main ingredients in the proof of [LRS]. We give a detailed analysis on those pseudo-densities that occurs in this proof and we characterizes them in the symmetric case. With this characterizations, we are able to state some optimality results for the lower bounds on the size of psd lifts of the correlation polytopes obtained by [LRS].

_{n}(n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORR_{n}grows exponentially in n.The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP.

In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORR

_{nn}. By the way, their work showed the first-known super-polynomial lower bounds on the size of psd lifts of any explicit family of polytopes.An elaboration of this work of [LRS] is the main part of our thesis. It is our objective and intention to present a very detailed version of their proof and in the ideal case a version that makes it easier to understand their brilliant work. In this connection, it is our motivation to bring their work to a broader number of people.

On the other hand, we present some of our own ideas by which we even obtain some slightly stronger results than [LRS] at some points. By the way, we illustrate way [LRS] could even show a stronger lower bound than they claimed in their original work.

On the whole, this thesis can be divided into three parts. The already mentioned proof of the work of [LRS] forms the second one. In the first part, we present a new and easier proof of a famous and often cited theorem of Grigoriev, where he proved lower bounds on the degree of the Real Nullstellensatz. On the one hand, Grigoriev's Theorem is on its own of high significance for questions concerning the power and complexity of algorithms relying on sums of squares and solving problems as they appear frequently in combinatorial optimization, on the other hand, this results is also essential for the work of [LRS]. We also present two applications of Grigoriev`s theorem respectively its proof.

In the last part of our thesis, we take a look on so-called pseudo-expectations and pseudo-densities, Boolean functions with specific properties, that are one of the main ingredients in the proof of [LRS]. We give a detailed analysis on those pseudo-densities that occurs in this proof and we characterizes them in the symmetric case. With this characterizations, we are able to state some optimality results for the lower bounds on the size of psd lifts of the correlation polytopes obtained by [LRS].

##### Summary in another language

##### Subject (DDC)

510 Mathematics

##### Keywords

Semidefinite Programming, Combinatorial Optimization, Correlation Polytope, PSD Rank, Symmetric Boolean Functions, Sums of Squares, Real Nullstellensatz

##### Conference

##### Review

undefined / . - undefined, undefined. - (undefined; undefined)

##### Cite This

## ISO 690

GRULER, Sebastian, 2018.*The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes*[Dissertation]. Konstanz: University of Konstanz

## BibTex

@phdthesis{Gruler2018stren-42935, year={2018}, title={The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes}, author={Gruler, Sebastian}, address={Konstanz}, school={Universität Konstanz} }

## RDF

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/42935"> <dc:contributor>Gruler, Sebastian</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-07-31T11:43:33Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:abstract xml:lang="eng">In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORR<sub>n</sub> (n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORR<sub>n</sub> grows exponentially in n.<br />The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP.<br />In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORR<sub>n</sub. Such spectrahedra are called psd lifts of CORR<sub>n</sub>. By the way, their work showed the first-known super-polynomial lower bounds on the size of psd lifts of any explicit family of polytopes.<br />An elaboration of this work of [LRS] is the main part of our thesis. It is our objective and intention to present a very detailed version of their proof and in the ideal case a version that makes it easier to understand their brilliant work. In this connection, it is our motivation to bring their work to a broader number of people.<br />On the other hand, we present some of our own ideas by which we even obtain some slightly stronger results than [LRS] at some points. By the way, we illustrate way [LRS] could even show a stronger lower bound than they claimed in their original work.<br />On the whole, this thesis can be divided into three parts. The already mentioned proof of the work of [LRS] forms the second one. In the first part, we present a new and easier proof of a famous and often cited theorem of Grigoriev, where he proved lower bounds on the degree of the Real Nullstellensatz. On the one hand, Grigoriev's Theorem is on its own of high significance for questions concerning the power and complexity of algorithms relying on sums of squares and solving problems as they appear frequently in combinatorial optimization, on the other hand, this results is also essential for the work of [LRS]. We also present two applications of Grigoriev`s theorem respectively its proof.<br />In the last part of our thesis, we take a look on so-called pseudo-expectations and pseudo-densities, Boolean functions with specific properties, that are one of the main ingredients in the proof of [LRS]. We give a detailed analysis on those pseudo-densities that occurs in this proof and we characterizes them in the symmetric case. With this characterizations, we are able to state some optimality results for the lower bounds on the size of psd lifts of the correlation polytopes obtained by [LRS].</dcterms:abstract> <dcterms:issued>2018</dcterms:issued> <dc:rights>terms-of-use</dc:rights> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/42935"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes</dcterms:title> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/42935/5/Gruler_2-nhez0onnpbps3.pdf"/> <dc:creator>Gruler, Sebastian</dc:creator> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/42935/5/Gruler_2-nhez0onnpbps3.pdf"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-07-31T11:43:33Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/"/> </rdf:Description> </rdf:RDF>

##### Internal note

##### xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

##### Examination date of dissertation

June 15, 2018

##### University note

Konstanz, Univ., Doctoral dissertation, 2018

##### Method of financing

##### Comment on publication

##### Alliance license

##### Corresponding Authors der Uni Konstanz vorhanden

##### International Co-Authors

##### Bibliography of Konstanz

No