DD3013 Sum of squares and integer programming relaxations
Table of Contents
Please check here for changes and updates
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.
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.
4.1 About the calendar
4.2 Location of the lecture room(s)
5 Reading material
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:
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:
Other useful resources are
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
The students will learn
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.
8.1 Scribe deadlines
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
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
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.