CSCI 5170: Computational Complexity

The Chinese University of Hong Kong, Spring 2016

Recent Announcements

Course Description

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
1Jan 12
Circuits: Decision trees, disjunctive normal form pdf
2Jan 19
Parallel computation: Small depth circuits pdf
3Jan 26
Sequential computation: Branching programs pdf
4Feb 2
Monotone circuits pdf
Feb 9
Lunar New Year holiday
5Feb 16
Algorithms: Deterministic, nondeterministic, randomized pdf
6Feb 23
Average-case complexity and one-way functions pdf
7Mar 1
Pseudorandom generators pdf
8Mar 8
Sublinear-time algorithms and quantum algorithms pdf
9Mar 15
Proofs: Randomness and interaction in proof systems pdf
10Mar 22
Refutations and statistical zero-knowledge pdf
11Mar 29
PCPs and approximation algorithms pdf
12Apr 5
Proof of the PCP theorem pdf
13Apr 12
Pseudorandom functions, learning, and natural proofs pdf
Apr 19
Project presentations


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


Notes will be provided for every lecture. The main reference is

Most of the material can be found in this book, although our emphasis and presentation may be different. The following two books are also recommended: