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

Lade...
Vorschaubild
Dateien
Gruler_2-nhez0onnpbps3.pdf
Gruler_2-nhez0onnpbps3.pdfGröße: 1.49 MBDownloads: 536
Datum
2018
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

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 CORRn</sub. Such spectrahedra are called psd lifts of CORRn. 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].

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
510 Mathematik
Schlagwörter
Semidefinite Programming, Combinatorial Optimization, Correlation Polytope, PSD Rank, Symmetric Boolean Functions, Sums of Squares, Real Nullstellensatz
Konferenz
Rezension
undefined / . - undefined, undefined
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Datensätze
Zitieren
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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
June 15, 2018
Hochschulschriftenvermerk
Konstanz, Univ., Diss., 2018
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen