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.
|Models: Decision trees|
|Sublinear-time computation 1|
|Sublinear-time computation 2|
|Applications: Pseudorandomness and cryptography|
|Natural proofs and learning|
|Holographic proofs (PCPs) and optimization|
|Interactive proofs and verification|
|Satisfiability, refutations, and phase transitions|
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.