LP/SDP Hierarchies Reading Group



Summary: Recently LP and SDP hierarchies have received  a lot of attention due to their potential to make progress on long standing algorithmic questions, and connections to various other areas such as computational complexity, combinatorial and polynomial optimization, quantum computing, proof complexity and so on. The goal will be to read and understand various recent results about LP and SDP hierarchies.

We usually meet at CWI (currently on Tuesday afternoons, but this may change depending of availability of people).
The exact time and location for each lecture will be posted below. The table below also has relevant reading material/slides for each lecture.

Below is also a tentative list of possibly interesting papers to present. If you would like to present one of the papers, or add some to this list, please let Nikhil or Monique know.



Lectures:

Date/Time Title Reading Material                                
1 Oct 2, Tu 15:00 (CWI, room L016) Introduction to Hierachies
Speaker: Monique

Slides
Most relevant to the lecture is: A comparison of the Sherali-Adams, Lov\'asz-Schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research, 28(3):470-496, 2003 (ps)

The chapter:  Semidefinite Programming and Integer Programming. With F. Rendl. In Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel (eds.), pages 393-514, Elsevier B.V., December 2005.
also discusses the hierarchies, as well as SDP based approximation results till 2004 about.  (ps)

A recent survey on hierachies by Chlamtac and  Tulsiani  (pdf)
2 Oct 9, Tu 15:00
(CWI, Room L016)
Introduction, part 2
Speaker: Monique
Same as above
3 Oct 30, Tu 15:00
(CWI, Room L016)
Parts of survey by  Chlamtac and Tulsiani 
Speaker: Nikhil  (Slides)
Survey by Chlamtac and  Tulsiani  (pdf)
Related slides by Tulsiani  (pdf)
4 Nov 13, Tu 15:00
CWI, Room L016
More on probabilistic view
Proving Lower bounds
Charikar, Markarychev, Makarychev: Integrality gaps for Sherali-Adams relaxations. STOC 2009. (pdf)
5 Nov 27, Tu 15:00
CWI, Room L016
Ruben talks about  Decomposition Lemma and Lasserre hierarchies for directed Steiner tree Directed Steiner Tree and the Lasserre Hierarchy. T. Rothvoss. (pdf)  (Slides on Rothvoss' webpage)
Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack
, Anna R. Karlin, Claire Mathieu and C. Thach Nguyen, IPCO 2011. (pdf)
6 Dec 7, Fr 14:00
CWI, Room L017
(note the diffferent day and time)
Ruben continues the above

7 Dec 11,   time 11:00
CWI, Room TBD
Monique talks about the proof of the Decomposition Lemma Monique's notes on the decomposition lemma.
8 Jan 18, 15:00, CWI, L016 Antonis talks about eigenvalues, embeddings, expansion and sparsest cut Notes of Luca Trevisan
9 March 1, 15:00
CWI,  L016
Jop talks  about the paper:
Hypercontractivity, sum-of-squares proofs, and their applications.. 
B. Barak, F. G. S. L. Brandao, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. STOC 2012. (pdf)
10 March 8, 15:00
CWI, L016
Jop's talk part 2. Same as above.
Related papers that were referred to in the talk.
A complete family of separability criteria ( by Doherty, Parillo, Spedalieri)
A quasipolynomial-time algorithm for the quantum separability problem (by Brandao, Christandl, Yard)
11 March 27, 15:00
CWI, L016
Konstantin Makarychev Charikar, Markarychev, Makarychev: Integrality gaps for Sherali-Adams relaxations. STOC 2009. (pdf)
12 June 14, 15:00, CWI, L016 Nikhil Bansal Prasad Raghavendra, Ning Tan. Approximating CSPs with global cardinality constraints using SDP
hierarchies. SODA 2012 (pdf)
13 Sep 11 (Wed), 15:00, Room L016 Daniel Dadush On the existence of 0/1 polytopes with high semidefinite extension complexity.  Based on the paper http://arxiv.org/abs/1305.3268  by J. Briet, D. Dadush, S. Pokutta
14 Sep 27 (Fri)
15:00, Room L016
Video Lecture + Discussion Approximate constraint satisfaction requires large LP relaxations.  Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer  (pdf)
 Video:  http://simons.berkeley.edu/talks/james-lee-2013-08-28
15 Oct 15 (Tue)
15:00, Room  L016
Ronald de Wolf   Part 2 of the discusssion on the paper above.
We will recap the main ideas, and discuss some technical details.
Some basic Fourier analysis on the boolean cube would be needed, which can be found for example
in this survey by Ronald.
16 April 3 (Thu)
11:00, Room L120
Monique Laurent Hierarchies of SDP bounds for quantum graph parameters.
Based on the preprint
 by Monique and Teresa:
http://arxiv.org/abs/1312.6643
17 April 23 (Wed)
11:00-12:00 
and 14:00 - 15:30
Room L016
Daniel Dadush
Nikhil Bansal
SoS proofs and applications of sparse vector problem
Fun blog article by Boaz: Fun and games with sums of squares  (pdf)
B. Barak, J. Kelner, and D. Steurer. Rounding Sum-of-Squares Relaxations (pdf)  STOC 2014
18 June 6 (Fri)
15:00-17:00
Ronald de Wolf The matching polytope has exponential extension complexity.
Thomas Rothvoss (pdf
19 Sept 5 (Friday)
15:00- 17:00, Room L017
Nikhil Bansal Independent sets in sparse graphs
20 Oct 10 (Friday)
15:00 - 17:00
Room L016
Sabine Burgdorf Hardness of the quantum chromatic number based on the paper
Binary Constraint System Games and Locally Commutative Reductions by Zhengfeng Ji  (pdf)


List of Papers (with links):


0.  An excellent recent survey (together with slides) by Rothvoss on recent use of Lasserre hierarchy in approximation algorithms.
   Slides  pdf

1. Coloring 3-colorable graphs: A couple of papers of Eden Chlamtac which use hierarchies to improve upon previous works.
(Possibly a hard read, as they also require understanding  tools of Blum'91  and measure concentration ideas of Arora-Rao-Vazirani).


2. O(n^1/4) approx for Dense-k-subgraph: This is a nice and readable paper making progress on the best known bounds for the dense-k-subgraph problem.


3. Using hierarchies for Directed Steiner Trees. A nice and clean paper. It also illustrates tools like
the Decomposition Lemma (of Mathieu et al)  for Lasserre in a nice way.

4.  Poly-log approximations for coloring 3-colorable graphs in some special cases. Very well written.


5. Sparsest cut in bounded treewidth graphs. Very clean and readable. (This is subtantially improved by paper 9 below).


6.   An alternate proof of the sub-exponential time algorithm for Unique Games due to Arora, Barak, Steurer.
Formalizes the idea of global vs local correlation  via threshold ranks of graphs.

7. Graph partitioning and max-bisection.


8.  Approximate constraint satisfaction requires large LP relaxations.  Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer  (pdf)
       Video:  http://simons.berkeley.edu/talks/james-lee-2013-08-28

9.  Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results. STOC 2013. Anupam GuptaKunal TalwarDavid Witmer  (pdf)

----------------

Lower Bounds:

1. Interesting connections to sum-of-squares, UGC, quantum computing.


2.  Very strong Lasserre gaps for dense-k-subgraph.

3. More on Lasserre lower bounds


4. Lower bounds for LS and SA hierarchies. 


5.  This is probably a nice introductory paper for how to show lower bounds. 


6.  UGC gap instances due to Khot-Vishnoi [FOCS 05] ,  and follow up works

7.  Sums of squares, moment matrics and optimization over polynomials. Survey by Monique Laurent.  (pdf)
      In Emerging Applications of Algebraic Geometry,M. Putinar and S. Sullivant (eds.), Springer, pages 157-270, 2009.

8.  Some recent applications of sums of squares