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 |
Notes will be provided for every lecture. The main reference is