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