This is an introductory course in computational complexity theory.
It is introductory in the sense that no prior knowledge in complexity theory is assumed.
However, I do assume a basic understanding of
algorithms and familiarity with the basics of theory of computation.
For example, I assume you know the Big-O notation,
algorithms on graphs (breadth first search, depth first search),
regular languages and finite automata,
and that you have seen Turing machines and know what is P and NP.
The latter concepts will also be introduced and reviewed in the course.
Further, I expect you
(1) have "mathematical maturity" (e.g., are comfortable with proofs and abstract reasoning);
(2) are interested in the material; and
(3) are willing to spend time outside of class in order to better
understand the material presented in lectures.
Complexity theory is one of the most elegant branches of computer science. The goal
of the course is to become familiar with some of the most beautiful results in our field.
Arora and Barak, Computational Complexity: A Modern Approach.
Copies of the textbook will be available in the library.
I will also provide lecture notes giving further details or covering topics not in that text.
If you are unsure whether this class is appropriate for you, I recommend
you look at the Arora-Barak textbook
to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate.
The text book
Michael Sipser, Introduction to the theory of computation,
contains the material we will cover in the first few weeks as well as the required
background for the class.
- 17.11.2016: Homework 2 is online.
- Tutorials will start from 08.11.2016. (01.11.2016 is a holiday!).
Additionally, we will have a special tutorial on 03.11.2016 to help
with the homework.
Readings refer to Arora-Barak.
In addition, we will post notes on individual lectures throughout the course
of the semester. Feedback and corrections on the lecture notes are always appreciated!
- [Week 1: 24.10.2016 26.10.2016]
Introduction; review of Turing machines; P and NP; NP-completeness
Reading: Chapter 0; Chapter 1: 1.1-1.6; Chapter 2: 2.1, 2.2, 2.4.
- [Week 2: 31.10.2016 and 02.11.2016]
Cook-Levin theorem (proof).
NP and coNP.
Structure of NP.
Reading: Chapter 2.
- [Week 3: 07.11.2016 and 09.11.2016]
Diagonalization. Hierarchy theorems.
Oracles and relativization.
We followed the first proof here
of Ladner's theorem.
- [Week 4: 14.11.2016 and 16.11.2016]
Space Complexity: PSPACE, L, NL.
QBF is PSPACE-complete.
PATH is NL-complete.
- [Week 5: 21.11.2016 and 23.11.2016]
NL = coNL. NFA-universality. P-completeness.
Alternation. Polynomial hierarchy.
- [Week 6: 28.11.2016 and 30.11.2016]
PH using oracles.
P/poly. Karp-Lipton theorem. Non-uniform complexity.
Kannan's theorem. Link to the original paper.
- [Week 7: 05.12.2016 and 07.12.2016]
Parity is not in AC0. (Theorem 14.4 in Arora-Barak.)
- [Week 8: 12.12.2016 and 14.12.2016]
Randomized computation. RP, BPP.
Schwarz-Zippel lemma and polynomial identity testing.
- [Week 9: 19.12.2016 and 21.12.2016]
Interactive proofs. MA and AM.
Interactive proof for coNP.
- [Week 10: 09.01.2017 and 11.01.2017]
IP = PSPACE.
- [Week 11: 16.01.2017 and 18.01.2017]
Cryptography. One-way functions. Encryption from one-way functions.
- [Week 12: 23.01.2017 and 25.01.2017]
Counting complexity. #P. Toda's theorem.
- [Week 13: 30.01.2017 and 01.02.2017]
- [Week 14: 06.02.2017 and 08.02.2017]