|
|
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/ |
| 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):
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.
----------------
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