TSP

Topics in Theoretical Computer Science

Credits 4
Lecturer Ola Svensson
Office hours Wednesdays 16-18 in INJ 112
Schedule Mondays 9:00-13:00 in CM 011

Short description

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced algorithmic techniques, and develop an understanding of fundamental questions that underlie some of the key problems of modern computer science.

For last year's course, please see here.

Assignments

(Preliminary) Schedule and references

 The probabilistic method Monday 9-13 February 16 CM 011 Reference book: "The probabilistic method" by N. Alon and J. H. Spencer.Scribes of Lecture 1
 Lovasz Local Lemma Monday 9-13 February 23 CM 011 Reference book: "The probabilistic method" by N. Alon and J. H. Spencer. Scribes of Lecture 2
 Expanders Monday 9-13 March 2 CM 011 Good reference here. Scribes of Lecture 3
 Bipartite Matchings, intro to LPs Monday 9-13 March 9 CM 011 Good reference here.Scribes of Lecture 4
 LP duality, Bipartite Matchings, Spanning trees Monday 9-13 March 16 CM 011 Good reference: "Understanding and using Linear Programming". Scribes of Lecture 5
 Matroids and Matroid Polytope Monday 9-13 March 23 CM 011 Good reference here.Scribes of Lecture 6
 Matroid Intersection Monday 9-13 March 16 CM 011 Good references here, Lectures 10-13 here, and here. Scribes of Lecture 7
 Matroid Intersection Polytope Monday 9-13 April 13 CM 011 Good reference here.Scribes of Lecture 8 Comment: guest lecture by Hyung-Chan An
 Perfect Matchings in General Graphs Monday 9-13 April 20 CM 011 Good reference here. Slides of Jakub's presentation: here
 Ellipsoid method Monday 9-13 April 27 CM 011 Good references: here and here.Scribes of Lecture 10
 Multiplicative weight update, simplex Monday 9-13 May 4 CM 011 Good references: "Understanding and using Linear Programming" and here.Scribes of Lecture 11
 Lower bounds on Extended Formulations Monday 9-13 May 11 CM 011 Scribes of Lecture 12
 Final Exam and Project Presentations Monday 9-13 May 18 CM 011 Good luck!

Grading

The grade will be based on problem sets [50%], scribe notes [15%], and final exam [35%] (that can be replaced by a project).

Scribe notes:

For each lecture, there will be one team (of one or two students) in charge of taking detailed notes, typing them in LaTeX, preparing any needed figures, and sending them to the lecturer within at most 72 hours after the lecture. These notes will be posted on the course website.
LaTeX is a typesetting language in which most (if not all) scientific literature is written. So, if you are not familiar with it yet, it is probably a good time to do it now.
To start, take a look at www.latex-project.org and play with our template. (Make sure you have a distribution installed and don't forget to put the preamble.tex and fullpage.sty files in the same directory as the template.)
When preparing scribe notes, please use this template -- just edit it to include your notes. (The template requires preamble.tex and fullpage.sty files to compile. Put them in the same directory.) Here are some guidelines regarding the style of the notes.
The target audience of these notes is you -- students -- a couple of weeks after the lecture, when you already have forgotten what it was about. Therefore, while scribing the notes, you should strive to present, in succinct, readable, and technically correct (but not too formal) way, all the important points and results of the lecture. A couple of more concrete suggestions: (Here is a collection of decent scribe notes (from a different course) that can serve as an example of the expected style and quality.)