CMPT 710

Computational Complexity   -   Spring 2015


  • Jan 7: This course is very likely to be cross-listed with cmpt 407 very soon. You will be getting emails once this happens. Meanwhile, let's move the next lecture (this Thu) already to be joint with cmpt 407: the time is 12:30-14:20, and the room is BLU 10021. See you there this Thu!

older announcements...

  • Jan 4: The first class is Tue, Jan 6.

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
  • barriers in complexity (relativization and natural proofs)
  • Computational Complexity: A modern approach by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009. [a new textbook, containing many 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
Tue 9:30-10:20 SECB 1012
Thu 9:30-11:20 SECB 1012
  • 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

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
Feb 3 Feb 24 Mar 17 Apr 7


Final exam:  Sat, Apr 18, 15:30-18:30, room TBA


I'll post homework assignments & solutions.

Lecture notes

I'll post my lecture notes for each class, and a reading assignment.