Home   •   Reading group: Lower bounds on SDP relaxations

Reading group: Lower bounds on SDP relaxations

The objective is to understand the paper: http://arxiv.org/abs/1411.6317, see also the lecture notes http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf.

We meet usually at 10:00 on Tuesdays for about 1 to 1.5 hours.

  1. April 26th at 10:00 in Amphi K (Guillaume)
    PSD rank and semidefinite extention complexity.
    Lifts of convex sets and cone factorizations, Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds and a survey
  2. March 29th at 10:00 in ?? (Antoine)
    Proof that nonnegative rank of the slack matrix corresponds to extension complexity
  3. March 22nd at 10:00 in Amphi K (Paul)
    A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
  4. March 8th, 2016 at 10:00 in Amphi J (Guillaume)
    La programmation linéaire (LP) et sa généralisation, la programmation semi-définie (SDP) sont des outils d'optimisation puissants et efficaces. On s'intéressera à la question suivante : à quel point peuvent-ils être utiles pour l'étude de problèmes NP-difficiles ? A moins que P=NP, on s'attend à ce que leur mise en oeuvre nécessite des ressources exponentielles.

    Plusieurs problèmes classiques (MAX-CUT, voyageur de commerce...) se ramènent à calculer le maximum d'une forme linéaire sur un polytope convexe. Savoir si l'approche LP (respectivement, SDP) est efficace revient à se demander s'il existe une description de ces polytopes utilisant un nombre polynomial d'inégalités linéaires (respectivement, d'inégalités pour l'ordre des matrices auto-adjointes). Il a été monté récemment que la réponse est négative : ces problèmes n'admettent aucune description polynomiale comme SDP (Lee--Raghavendra--Steurer, Best Paper Award à STOC'2015).

    Le but du groupe de travail est de comprendre ces travaux en ne supposant
    AUCUNE connaissance préalable. Lors de la séance introductive
    j'expliquerai la motivation, j'énoncerai précisément le résultat principal
    et je donnerai une idée de l'approche utilisée par les auteurs.

    Références :
    article original
    http://arxiv.org/abs/1411.6317

    notes d'un mini-cours de James Lee, beaucoup plus abordable
    http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

Published on