
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 SheraliAdams, Lov\'aszSchrijver and Lasserre
relaxations for 01 programming. Mathematics of Operations Research,
28(3):470496, 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 393514, 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
SheraliAdams 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 Semidefinite 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, sumofsquares proofs, and their applications.. 
B. Barak, F. G. S. L. Brandao, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. Hypercontractivity, sumofsquares 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 quasipolynomialtime 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 SheraliAdams 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/ 
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:0012: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 SumofSquares Relaxations (pdf) STOC 2014 
18  June 6 (Fri) 15:0017: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):
1.
Coloring 3colorable 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 AroraRaoVazirani).
2.
O(n^1/4) approx for Denseksubgraph: This is a nice and readable paper
making progress on the best known bounds for the denseksubgraph
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.
Polylog approximations for coloring
3colorable 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 subexponential 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 maxbisection.

Lower
Bounds:
1. Interesting connections to sumofsquares, UGC, quantum computing.
2. Very strong Lasserre gaps for denseksubgraph.
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
KhotVishnoi [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 157270, 2009.
8. Some recent applications of sums of squares