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...
Thumbnail Image
Date
2018
Editors
Contact
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
DOI (citable link)
ArXiv-ID
International patent number
Link to the license
EU project number
Project
Open Access publication
Restricted until
Title in another language
Research Projects
Organizational Units
Journal Issue
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 CORRn (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 CORRn 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 CORRnn. 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 690GRULER, 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&lt;sub&gt;n&lt;/sub&gt; (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&lt;sub&gt;n&lt;/sub&gt; grows exponentially in n.&lt;br /&gt;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.&lt;br /&gt;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&lt;sub&gt;n&lt;/sub. Such spectrahedra are called psd lifts of CORR&lt;sub&gt;n&lt;/sub&gt;.  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.&lt;br /&gt;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.&lt;br /&gt;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.&lt;br /&gt;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.&lt;br /&gt;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
Contact
URL of original publication
Test date of URL
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
Refereed