CMPT 407/710

Computational Complexity   -   Fall 2019


  • Dec 7: Solutions to Quiz 4 are posted.

older announcements...

  • Nov 24: The solutions to HW 4 are now posted.
  • Nov 12: HW 4 is now available. The solutuions to Quiz 3 are now posted.
  • Nov 3: Quiz 3 will cover the material from Lecture 17 - 23 (inclusive). I'll be out of town that Friday, so the quiz will be conducted by the TA, and no office hours next Friday.
  • Nov 3: The solutions to HW 3 are now posted.
  • Oct 22: The solutions to Quiz 2 are now posted. HW 3 is also posted.
  • Oct 10: Quiz 2 next Friday (Oct 18) will cover the material from Lecture 9 - 16 (inclusive). I'll be out of town that Friday, so the quiz will be conducted by the TA, and no office hours next Friday. (If you have questions on the material, you can ask me after the class next Wednesday.)
  • Oct 1: My office hours for this course will be Friday, 1:30 - 2:20 pm only. (That is, no office hours on Wednesday!)
  • Oct 1: The solutions to Quiz 1 are now posted; the password is in your email. HW 2 is now posted.
  • Sep 27: Quiz 1 is tomorrow (Fri). It will cover the material in Lectures 1-8 (inclusive); this is essentially the material on HW 1.
  • Aug 30: The first class is on Wed, Sep 4.

Course description

The main goal of Complexity Theory is to answer the question: What can be efficiently computed given limited resources? This is a more "practical" version of the main question of Computability Theory: What can be computed? In this course, we will see a rich landscape of complexity classes that are used to characterize problems according to the required resources (such as time, space, randomness, parallelism). We will discuss some known and conjectured relationships among these classes, obtaining a detailed map of the complexity world. Proving the correctness of this map would involve solving some of the deepest open problems in computer science, including the famous "P vs. NP" question.

  • Topics
  • Texts
  • Lectures
  • Office hours
  • Marking scheme
  • basic complexity classes (time, space, nondeterminism)
  • circuit complexity
  • NP-completeness
  • randomized computation complexity
  • polynomial-time hierarchy
  • counting classes
  • interactive proofs
  • the PCP theorem
  • quantum computing
  • barriers in complexity (relativization and natural proofs)
  • Computational Complexity: A modern approach by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009. [contains many fairly recent results in complexity]
  • Computational Complexity by Christos H. Papadimitriou, Addison-Wesley, 1995. [a classic; very comprehensive coverage]
  • Introduction to the Theory of Computation by Michael Sipser, 2012, 9781133187790. [intro into computability and complexity]
day time room
Mon 14:30-15:20 SECB1011
Wed 14:30-15:20 SECB1011
Fri 14:30-15:20 SECB1011
day time room
Fri 13:30-14:20 TASC1 8011
  • 4 in-class quizzes, worth 15% each,
  • final exam, worth 40%
Note: I will post 4 homework assignments (one before each quiz), which will not be collected and graded. The solutions to homework problems will be posted before the quiz. The quizzes will be loosely based on the homework problems, so you will benefit by solving the homework problems by yourself!

Teaching staff

Instructor: Valentine Kabanets (, Office: TASC1 8011

TA: Sophie Oh (

If you have grading-related questions, please email the TA and ask for an appointment. If you still have questions after meeting with the TA, then come and see me.

Important dates

The 50-minute quizzes will be given during our regular lectures on the following dates.

Quiz 1 Quiz 2 Quiz 3 Quiz 4
Sep 27 Oct 18 Nov 8 Nov 29


Final exam: Sat, Dec 14, 12:00–15:00, SSCC 9000


I'll post homework assignments & solutions.

Lecture notes & Slides

I'll post my lecture notes & slides for each class, as well as a reading assignment (usually from the book by Arora and Barak, unless specified otherwise).