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.
||Circuits: Decision trees, disjunctive normal form|
||Parallel computation: Small depth circuits|
||Sequential computation: Branching programs|
||Lunar New Year holiday|
||Algorithms: Deterministic, nondeterministic, randomized|
||Average-case complexity and one-way functions|
||Sublinear-time algorithms and quantum algorithms|
||Proofs: Randomness and interaction in proof systems|
||Refutations and statistical zero-knowledge|
||PCPs and approximation algorithms|
||Proof of the PCP theorem|
||Pseudorandom functions, learning, and natural proofs|
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