Computational complexity is the mathematical study of computational (in)efficiency. In this year's lectures, besides learning about basic techniques, I will try to say a bit about how computational complexity informs what is feasible and infeasible in other information processing areas (cryptographic protocols, combinatorial optimization, "big data" computations, machine learning, game theory and economics).
This course is a must for serious students of the theory of computing. It is also relevant to any discipline where computation plays a role, including cryptography, optimization, learning, data analysis, information theory, and combinatorics.
| date | topic | notes | |
|---|---|---|---|
| 1 | Sep 2 Sep 3 |
Models: Decision trees | |
| 2 | Sep 9 Sep 10 |
Parallel computation | |
| 3 | Sep 16 Sep 17 |
Sequential computation | |
| 4 | Sep 23 Sep 24 |
Sublinear-time computation 1 | |
| 5 | Sep 30 Oct 8 |
Sublinear-time computation 2 | |
| 6 | Oct 14 Oct 15 |
Quantum computation | |
| 7 | Oct 21 Oct 22 |
Efficient computation | |
| 8 | Oct 28 Oct 29 |
Applications: Pseudorandomness and cryptography | |
| 9 | Nov 4 Nov 5 |
Natural proofs and learning | |
| Nov 11 Nov 12 |
Classes cancelled by university | ||
| 10 | Nov 18 Nov 19 |
PCPs and optimization | |
| 11 | Nov 25 Nov 26 |
Interactive proofs and verification | |
| TBA | Project presentations |
Three homeworks and a take-home midterm exam will be issued throughout the semester.
You are encouraged to collaborate on the homeworks as long as you write up your own solutions and provide the names of your collaborators. I discourage you from looking up solutions to homework problems online, unless you have exhausted all other resources; if you do so, please provide proper credit and make sure you understand the solution before you write it.
Notes will be provided for every lecture. Here are some additional references.