CSI 5138: Computational Complexity

University of Ottawa, Fall 2023

Recent Announcements

Teaching Staff

name email office office hour
Andrej Bogdanov
abogdano@uottawa.ca SITE 5068 Fr 2–4

Course Description

Complexity theory is the study of problems that are hard for computers. How can we tell whether a problem is truly intractable or a better algorithm is in the cards? We will see some ingenious methods that complexity theorists have developed for this purpose over the past half-century.

The hallmark of complexity is a unified view of computation, which is why its insights are relevant throughout computer science (e.g., in cryptography, optimization, machine learning, and quantum computing). We will highlight such connections with other areas in this course.


week topic
1 Sep 6 Hardness by counting
Shannon’s theorem
2 Sep 13 Parallel computation
Håstad’s theorem
3 Sep 20 Sequential computation
Barrington’s theorem
4 Sep 27 Sublinear-time computation
Huang’s theorem
5 Oct 4 Quantum computation
the Bennett-Bernstein-Brassard-Vazirani theorem
6 Oct 11 P, NP, and all that
the Cook-Levin theorem
7 Oct 18 Average-case hardness and pseudorandom generators
the Nisan-Wigderson theorem
Oct 25 Reading Week
8 Nov 1 Cryptography, learning, and natural proofs
the Razborov-Rudich barrier
9 Nov 8 Interactive proofs
the Babai-Moran and Goldwasser-Sipser theorems
10 Nov 15 Refutations and statistical zero-knowledge
Okamoto's theorem
11 Nov 22 Heuristics and meta-complexity
Hirahara’s theorem
Nov 24 Project presentations (230-430 in SITE 5-084)


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.

You are not allowed to collaborate on the take-home midterm exam.

You can upload your solutons here or bring them to class.

Course Information


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