Topics in Theoretical Computer Science

Credits 
4 

Lecturer 
Ola Svensson 

Office hours 
Wednesdays 1618 in INJ 112 

Schedule 
Mondays 9:0013:00 in CM 011

Short description
The students gain an indepth 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
 First assignment available here. Deadline 09:15 Monday, March
16.
 Second assignment available here. Deadline 09:15 Monday, March
30.
 Third assignment available here. Deadline 12:00 AM Tuesday, April
21.
 Fourth assignment available here. Deadline 12:00 AM Friday, May
8.
(Preliminary) Schedule and references
The probabilistic method 
Monday 
913 
February 16 
CM 011 
Reference book: "The probabilistic
method" by N. Alon and J. H. Spencer.Scribes of Lecture 1 
Lovasz Local Lemma 
Monday 
913 
February 23 
CM 011 
Reference book: "The probabilistic
method" by N. Alon and J. H. Spencer. Scribes of Lecture 2 
Expanders 
Monday 
913 
March 2 
CM 011 
Good reference here. Scribes of Lecture 3 
Bipartite Matchings, intro to LPs 
Monday 
913 
March 9 
CM 011 
Good reference here.Scribes of Lecture 4 
LP duality, Bipartite Matchings, Spanning trees 
Monday 
913 
March 16 
CM 011 
Good reference: "Understanding and using Linear Programming". Scribes of Lecture 5 
Matroids and Matroid Polytope 
Monday 
913 
March 23 
CM 011 
Good reference here.Scribes of Lecture 6 
Matroid Intersection 
Monday 
913 
March 16 
CM 011 
Good references here, Lectures 1013 here, and here. Scribes of Lecture 7 
Matroid Intersection Polytope 
Monday 
913 
April 13 
CM 011 
Good reference here.Scribes of Lecture 8 Comment: guest lecture by HyungChan An 
Perfect Matchings in General Graphs 
Monday 
913 
April 20 
CM 011 
Good reference here. Slides of Jakub's presentation: here 
Ellipsoid method 
Monday 
913 
April 27 
CM 011 
Good references: here and here.Scribes of Lecture 10 
Multiplicative weight update, simplex 
Monday 
913 
May 4 
CM 011 
Good references: "Understanding and using Linear Programming" and here.Scribes of Lecture 11 
Lower bounds on Extended Formulations 
Monday 
913 
May 11 
CM 011 
Scribes of Lecture 12 
Final Exam and Project Presentations 
Monday 
913 
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.latexproject.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:
 Start by briefly summarizing the main topics discussed in the lecture;
 Try to use full sentences/prose  avoid bullet points;
 (Very important) Make sure to also include the motivation, illustrative examples and intuitions related to the presented concepts/algorithms/proofs  either the ones presented in the lecture or (even better!) the ones you came up on your own;
 If there is a simple figure that you feel would be helpful in understanding something, try to include it too;
 Make sure that all the formal arguments are correct and do not have any gaps in reasoning  if something in the argument is unclear to you, just email the lecturer for clarification.
 Polish the language and spell check your notes before sending them to the lecturer;
(
Here is a collection of decent scribe notes (from a different course) that can serve as an example of the expected style and quality.)