DD3013 Sum of squares and integer programming relaxations

Please check here for changes and updates

• 2014-5-9 Get the fifteenth lecture notes.
• 2014-4-28 The final problem set is online! Get it here
• 2014-4-21 Get the thirteenth and fourteenth lecture notes (not reviewed).
• 2014-4-8 Get the eleventh and twelfth lecture notes (not reviewed).
• 2014-3-29 The lecture of Monday 31st of March will be given by David Steurer.
• 2014-3-17 Check the new room for April 1st and 8th.
• 2014-3-17 Get the ninth and tenth lecture notes (not reviewed).
• 2014-3-3 Get the seventh and eighth lecture notes (not reviewed).
• 2014-2-27 The half course problem set is online! Get it here
• 2014-2-27 The topics of week 10 and 13 have been swapped.
• 2014-2-24 Get the fifth and sixth lecture notes (not reviewed).
• 2014-2-15 Get the third and fourth lecture notes (not reviewed).
• 2014-2-13 New reading material.
• 2014-1-30 New details about scribing/reviewing lecture notes.
• 2014-1-30 Grab the LaTeX sources for the lecture notes.
• 2014-1-29 Get the second lecture note.
• 2014-1-28 Get the first lecture note.
• 2014-1-27 Get the syllabus of the class here.
• 2014-1-27 Some changes in the reading material. This will happen very often as I set up lectures and as the guest lecturer define their material.
• 2014-1-21 The schedule of the first week just changed.
• 2014-1-13 Johan Håstad is also going to give two guest lectures. That's great!
• 2014-1-7 Per Austrin is going to give two guest lectures. Lucky students!
• 2014-1-6 Some lectures will be given in room 1440 (former library room at 4th floor)
• 2014-1-3 Now we have a calendar of the course. Some room are still missing because carpet booking took place and in some days room 4325 is not available.
• 2013-10-18 The page of the course is online, but it is still in progress.

Get the syllabus of the class here. You may also find useful to download the notation file.

I am the main lecturer and I am responsible for all aspects of the course. Office hours are only by appointment: please send an e-mail to schedule a meeting. I will likely arrange a formal student session after each homework.

• Final problem set (download)
• Half course problem set (download)

This is a tentative schedule of the course. Both the calendar and the content of some lectures may change. In particular we still need to organize guest lectures. Room 1440 is a backup solution since room 4523 was not available in some dates. I will try to find a better location in time for the guest lectures.

This list will be updated as we go on with the lectures

Lectures will be as self contained as possible, but students may find useful to refer to surveys and papers. In the first part of the course we introduce integer programming relaxations and we discuss their relation with approximation algorithms. The material for this part of the course is the following:

• Matouṧek and Gӓrtner Understanding and using linear programming. Springer, Berlin New York, 2007. (book)
• Gӓrtner and Matouṧek Approximation Algorithms and Semidefinite Programming Springer, Berlin New York, 2012. (book)
• Lovász Semidefinite programs and combinatorial optimization. In “Recent advances in algorithms and combinatorics” pp. 137-194. Springer 2003. (pdf)
• Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research 28, 470 (2001). (pdf)
• Rothvoß, The Lasserre hierarchy in Approximation algorithms (2013). (pdf)

In the second part of the course we will focus on rank lower bounds for sum of squares system. The results we will discuss come from some of the following papers:

• Grigoriev Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science 259, 613 (2001). (www)
• Schoenebeck Linear level Lasserre lower bounds for certain k-CSPs. Foundations of Computer Science (2008). (www)
• O'Donnell, Wright, Wu, Zhou Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. ACM-SIAM Symposium on Discrete Algorithms (2014). (www)
• Grigoriev Complexity of Positivstellensatz proofs for the knapsack. Computational complexity 10, 139 (2001). (www)
• O'Donnell & Zhou Approximability and proof complexity. ACM-SIAM Symposium on Discrete Algorithms (2013). (www)
• Barak, Gopalan, Håstad, Meka, Raghavendra and Steurer Making the Long Code Shorter. Foundations of Computer Science (2012). (www)

Other useful resources are

• Laurent, Sums of squares, moment matrices and optimization over polynomials. Emerging applications of algebraic geometry, 157 (2009). (pdf)
• Chlamtáč & Tulsiani, Convex relaxations and integrality gaps. Handbook on Semidefinite, Conic and Polynomial Optimization (2012). (pdf)
• Barak, Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, a survey about sum of squares proofs and connections with Unique Games Conjecture. To appear in the International Congress of Mathematics 2014. (www)
• A blog post by Boaz Barak on sum of squares. (www)
• The lecture notes of Pablo Parrilo course of Algebraic Techniques and Semidefinite Optimization. (www)
• Centrum Wiskunde & Informatica (CWI), in Amsterdam, has a reading group which focuses on some of the topics of this course. The page of this group contains a lot of additional resources and pointers.

  LP/SDP Hierarchies Reading Group

The course is open to anyone, but it is mainly targeted to PhD students and advanced Master's students.

The course requires mathematical maturity (i.e., the ability to follow a mathematical argument and to understand a formal proof). The students should be comfortable with the material covered by either DD1352 Algorithms, Data Structures, and Complexity, DD2354 Algorithms and Complexity or by corresponding courses at other universities. They will also need to know basic linear algebra, basic probability theory and a little bit of linear programming. The course is taught in English and all the material is in English, too.

This is a research oriented course: the purpose is to learn about sum of squares and its subsystems, which are subjects of active and high-quality research in theoretical computer science. At the end of the course students will be able to read specialized conference papers about the course's topics. They will learn about hierarchies of integer programming relaxations, integrality gaps and semidefinite positive programming. In particular the course aims to

• present integer programming relaxation hierarchies;
• introduce the sum of squares system;
• give examples of algorithms employing such relaxations;
• show lower bounds for sum of squares.

The students will learn

• what the linear and semidefinite positive relaxations of an integer program are;
• a little about how such relaxations are used to obtain approximation algorithms;
• about the limitation of sum of squares;
• about an important part of current research in theoretical computer science.

The course is worth 6 credits, and there will be 2 problem sets and scribe notes duty. I expect students to submit their homework in English, and to produce them with tools that have good support for math (of course LaTeX is strongly suggested). In order to succeed the students should pass all the problem sets and do a certain amount of scribe notes (the actual amount will depend on the number of people taking the course for credit).

The idea is that every student will write two lecture notes, and will review two lecture notes. Each such effort will have its own deadline. I already scribed the first two lecture notes and provided a template.

We have a Google Spreadsheet to assign the scribe/reviewer duties, which can be accessed and modified by the students. If you don't have the link please email me.

Most combinatorial optimization problems have a natural formulation as integer linear programs. Unfortunately it is hard to solve such programs, so we settle for less: we look for a fractional solution and then we round it to an integer one. This process usually gives a solution far from optimal.

Mathematicians and computer scientists have developed ways to improve the quality of solutions: they introduce new constraints that are valid for all integer solutions, but may exclude some fractional ones.

This process is formalized by the sum of squares inference system, which is a way to deduce such new constraints. This is the strongest system known in current literature and subsumes many successful techniques in approximation.

In the course we will discuss sum of squares and some of its subsystems, and the performance of certain systematic ways to produce the new constraints: for some problems we can get good approximation algorithms, while for others the systematic approach is too expensive. In particular we will focus on rank lower bounds, which give a way to measure how hard a problem is for sum of squares.

The course is made of two parts:

In the first part we introduce sum of squares and its many subsystems. It is important to spend some time on the subsystems because most lower bounds in literature are for them. We will also briefly introduce semidefinite positive programming and semidefinite positive relaxations.

In the second part of the course we will study rank for optimization problems like \(3\)-SAT, \(3\)-XOR, Knapsack, Planted Clique, Densest \(k\)-subgraph.