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.
|1||Oct 2, Tu 15:00 (CWI, room L016)||Introduction to Hierachies
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
|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
|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
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
|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
|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
|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
|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
On Chan, James R. Lee, Prasad Raghavendra, David Steurer
|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
of SDP bounds for quantum graph parameters.
Based on the preprint by Monique and Teresa:
|17||April 23 (Wed)
and 14:00 - 15:30
|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)
|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
|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):
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.
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.
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