CSCI 5170: Computational Complexity

The Chinese University of Hong Kong, Fall 2019

Recent Announcements

Course Description

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.

Lectures


date topic notes
1Sep 2
Sep 3
Models: Decision trees pdf
2Sep 9
Sep 10
Parallel computation pdf
3Sep 16
Sep 17
Sequential computation pdf
4Sep 23
Sep 24
Sublinear-time computation 1 pdf
5Sep 30
Oct 8
Sublinear-time computation 2
6Oct 14
Oct 15
Quantum computation pdf
7Oct 21
Oct 22
Efficient computation pdf
8Oct 28
Oct 29
Applications: Pseudorandomness and cryptography
9Nov 4
Nov 5
Natural proofs and learning
10Nov 11
Nov 12
Holographic proofs (PCPs) and optimization
11Nov 18
Nov 19
Interactive proofs and verification
12Nov 25
Nov 26
Satisfiability, refutations, and phase transitions
TBA Project presentations

Homeworks

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.

Course Information

References

Notes will be provided for every lecture. Here are some additional references.