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.
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 tradeoffs 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
 Boolean circuits and nonuniform computation
 Role of randomness in computation
 Interactive proofs and zeroknowledge proofs
 Probabilistically checkable proofs and their characterization of the complexity class NP (PCP Theorem)
 Communication complexity
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.
Assignments
 First assignment available here. Deadline 12:00 Tuesday, March
22.
 Second assignment available here. New Deadline 9:00 Monday, April
11.
 Third assignment available here (fixed small typo). Deadline 16:00 Thursday, April
28.
 Fourth assignment available here (made small clarification). Deadline 9:00 Monday, May
23.
Schedule and references
 Lecture 1: Introduction. Diagonalization. Time hierarchy theorem. Chapter 03. Another good reference is here. Introductory slides. Ola's notes.
 Lecture 2: Nondeterministic computation, P vs P, and why diagonalization alone won't resolve P vs NP. Chapter 23.Recall last lecture slides. Ola's notes.
 Lecture 3: Boolean circuits (nonuniform computation), an alternative proof of NPcompleteness. Chapter 6. Ola's notes.
 Lecture 4: Randomized computation, Adleman's Theorem. Chapter 7. Ola's notes.
 Lecture 5: Polynomial hierarchy. KarpLipton Theorem. Chapter 5 and 6. Ola's notes.
 Lecture 6: Natural Proofs. Interactive Proofs. Chapter 8 and 23. Ola's notes.
 Lecture 7: Interactive Proofs. IP=PSPACE Chapter 8. Ola's notes.
 Lecture 8: Probabilistic Checkable Proofs. Local Testability and Decodability of WalshHadamard Code Chapter 11. Ola's notes.
 Lecture 9: Probabilistic Checkable Proofs. NP is a subset of PCP(poly(n), 1). Chapter 11. Ola's notes.
 Lecture 10: Hardness of Approximation. Start of Quantum Computing Chapters 11 and 10. Ola's notes.
 Lecture 11: Definition of Quantum Computing, Grover's Search Algorithm Chapter 10. Ola's notes.
Grading
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.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.)