School of
Computer Science
and Communication
DD3013 Spring 2014

KTH / CSC / Courses / DD3013 / DD3013 Spring 2014

# DD3013 Sum of squares and integer programming relaxations

## 1 News

• 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-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.

## 2 Lecturer: Massimo Lauria

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.

## 4 Schedule

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.

Lecture Time Room Week Topic
1. 28 Jan, Tue - 10:00-12:00 4523 05 Integer and linear programming; integrality gaps. (notes)
2. 30 Jan, Thu - 14:00-16:00 4523 05 SDP programming and SDP duality. (notes)
3. 3 Feb, Mon - 10:00-12:00 1440 06 LP and SA relaxations (notes)
4. 4 Feb, Tue - 10:00-12:00 4523 06 SDP relaxations: sum of squares, Lasserre, Positivstellensatz (notes)
5. 10 Feb, Mon - 10:00-12:00 4523 07 Properties of the Lasserre Relaxation (notes)
6. 11 Feb, Tue - 10:00-12:00 4523 07 Upper bounds and approximation algorithms (notes)
7. 17 Feb, Mon - 10:00-12:00 4523 08 Sum of squares lower bounds for 3-SAT and 3-XOR (I) (notes)
8. 18 Feb, Tue - 10:00-12:00 4523 08 Sum of squares lower bounds for 3-SAT and 3-XOR (II) (notes)
9. 3 Mar, Mon - 10:00-12:00 4523 10 Graph Isomorphism and the Lasserre Hierarchy (I) (notes)
10. 4 Mar, Tue - 10:00-12:00 4523 10 Graph Isomorphism and the Lasserre Hierarchy (II) (notes)
11. 24 Mar, Mon - 10:00-12:00 4523 13 Rank lower bound for knapsack (I) (notes)
12. 25 Mar, Tue - 10:00-12:00 4523 13 Rank lower bound for knapsack (II) (notes)
13. 31 Mar, Mon - 10:00-12:00 4523 14 Short Codes and Sum of Squares (I) (David Steurer) (notes)
14. 1 Apr, Tue - 10:00-12:00 D4448 14 Short Codes and Sum of Squares (II) (Johan Håstad) (notes)
15. 7 Apr, Tue - 10:00-12:00 4523 15 Sum of Squares proof of KKL theorem (I) (Per Austrin) (notes)
16. 8 Apr, Tue - 10:00-12:00 D4448 15 Sum of Squares proof of KKL theorem (II) (Per Austrin)

• Week 4 (Jan 20 - Jan 26): Banff 2014 workshop: no lectures.
• Week 9 (Feb 24 - Mar 1): is school vacation: no lectures.
• Week 11 (Mar 10 - Mar 13): study period.
• Week 12 (Mar 14 - Mar 21): exams for Ms Students.
• Week 16-17: Easter.

### 4.2 Location of the lecture room(s)

• Rooms 4523 (5th floor) and 1440 (4th floor) are located at CSC in the main campus of KTH. There are at least three entrances to the building: Lindstedtsvägen 3, 5 and Osquars backe 2, (the latter is entrance with elevator, no stairs)
• Subway stop: Tekniska Högskolan (red line, direction )

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.

## 6 Prerequisites

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.

## 7 Expected outcome

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.

## 8 Evaluation

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.

Deadlines will more or less follow the following scheme: by Friday night of a certain week I'd like to see the submissions of the lecture notes for the lectures of that week.

In this way I will be able to do a quick pass during the weekend. On sunday evening I will send the lecture notes to the reviewer. The reviewed lecture notes will be needed by wednesday evening. My hope is to have the lecture notes on the webpage before the next weekend. Any delay from my part will be compensated by a corresponding extension of your individual deadlines.

### 8.2 How to submit lecture notes: email

The preferred way to submit lecture notes is using github, which is a platform for collaborative programming. I understand that not all of you may want to set that up, and it is indeed non trivial if you've never done that before.

Thus it is alway possible to sort out the scribe and review duties just by sending your work to me by email.

You can get the LaTeX sources, templates and the source of lecture 1 (to read as an example) here.

### 8.3 How to submit lecture notes: the GitHub way

There is github repository at https://github.com/MassimoLauria/sos14-handout where you can post your scribe notes and your fix. The scheme is the following:

1. the scribe/reviewer will fork my repository;
2. scribes/reviewers will send pull requests to me to add data to the repository, as often as they feel reasonable;

It is always a good idea to do small commits and to commit often to your own repository, but please do not flood me with pull requests. It is fine to send me few revisions instead of a single monolithic pull request, but please be moderate. Your own repository instead is your realm and you do as you wish (this is one of the beauties of distributed version control systems).

If you need help with git and github I am sure some of your colleagues will be generous. Please sort out git and github as soon as possible.

Lecture notes that are under scribing/review process by one of your colleagues should not be edited by anyone else until “released”. Nevertheless everyone is allowed to send pull requests with fixes and improvements to the released notes and to the notation file. A significant effort in this direction may have a limited positive influence to the grade. You are encouraged to fix, spell check and improve the notes for the first two lectures at any time. This would be particularly appreciated.

## 9 Description of the course

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.