## DD3013 Sum of squares and integer programming relaxations## Table of Contents## 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-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. ## 2 Lecturer: Massimo LauriaI 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
## 4.1 About the calendar**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 )
## 5 Reading material
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 PrerequisitesThe 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 ## 7 Expected outcomeThis 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
The idea is that every student will 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 deadlinesDeadlines 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: emailThe 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 - the scribe/reviewer will fork
**my**repository; - 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
Lecture notes that are under scribing/review process by one of your
colleagues should not be edited by anyone else until “released”.
Nevertheless ## 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 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 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. |