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.

This year's course will concentrate on exciting results in computational complexity. Computational complexity is the part of computer science that studies the computational resources (time, memory, communication, ...) needed to solve problems that we care about. It also looks at the trade-offs and relationships between different types of computation ( e.g. whether randomness helps, exact vs approximate solutions, average vs worst case guarantees, ...). After starting with basic concepts, potential topics include

Recommended book: Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. A draft of the book is available for free here.

For previous editions of the course (covering different topics), see 2014 and 2015.


Schedule and references


The grade will be based on problem sets [60%], and a final exam [40%] (that can be replaced by a project). In addition, bonus credits will be given for note scribing.

Scribe notes:

For lectures that need scribes, 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.)