Computational complexity is the mathematical study of computational efficiency. It is concerned with identifying efficient models of computation and understanding their power, their limitations, and their interrelationships.
In this offering we will emphasize models that come up in modern information processing applications (such as cryptographic protocols, combinatorial optimization, "big data" computations, machine learning). The methodology is mathematically rigorous in the style of the theory of computing.
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 | Jan 12 |
Circuits: Decision trees, disjunctive normal form | |
2 | Jan 19 |
Parallel computation: Small depth circuits | |
3 | Jan 26 |
Sequential computation: Branching programs | |
4 | Feb 2 |
Monotone circuits | |
Feb 9 |
Lunar New Year holiday | ||
5 | Feb 16 |
Algorithms: Deterministic, nondeterministic, randomized | |
6 | Feb 23 |
Average-case complexity and one-way functions | |
7 | Mar 1 |
Pseudorandom generators | |
8 | Mar 8 |
Sublinear-time algorithms and quantum algorithms | |
9 | Mar 15 |
Proofs: Randomness and interaction in proof systems | |
10 | Mar 22 |
Refutations and statistical zero-knowledge | |
11 | Mar 29 |
PCPs and approximation algorithms | |
12 | Apr 5 |
Proof of the PCP theorem | |
13 | Apr 12 |
Pseudorandom functions, learning, and natural proofs | |
Apr 19 |
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. The main reference is