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
- Boolean circuits and nonuniform computation
- Role of randomness in computation
- Interactive proofs and zero-knowledge proofs
- Probabilistically checkable proofs and their characterization of the complexity class NP (PCP Theorem)
- Communication complexity
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 0-3. 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 2-3.Recall last lecture slides. Ola's notes.
- Lecture 3: Boolean circuits (non-uniform computation), an alternative proof of NP-completeness. Chapter 6. Ola's notes.
- Lecture 4: Randomized computation, Adleman's Theorem. Chapter 7. Ola's notes.
- Lecture 5: Polynomial hierarchy. Karp-Lipton 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 Walsh-Hadamard 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.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.
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.)
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;