Complexity of Computation: CPSC506
2016 Winter Term 1

This course covers central topics in complexity theory, as well as quantum and molecular models of computing. Topics include: time and space bounded complexity classes, randomized complexity classes, interactive proof systems, finding approximate solutions to hard optimization problems and recognizing when problems are had to approximate, quantum complexity theory, models of computing with molecules.

You should already be familiar with Turing machines, what it means for a problem to be decidable, the complexity classes P and NP, and NP-completeness (Arora and Barak Chapters 1 and Chapter 2 up to section 2.5).

Place and Time
09:00-10:30 MW
101 DMP

Anne Condon
Office: X551 CS
Email: condon at
Office Hours: After class or by appointment - don't hesitate to get in touch

Computational Complexity
by S. Arora and B. Barak, Cambridge University Press, 2009
Draft available on-line
Contains links to on-line graduate notes

The Nature of Comutation
by Christopher Moore and Stephen Mertens
Full text online in the UBC Library

Quantum Information and Quantum Computing
Lecture Notes by John Watrous

Theory of Molecular Computing
Lecture Notes by Dave Doty

Course Schedule

Date Resources
Wed, Sep 7 Course Overview and Pre-req Review
Reading: Arora-Barak 1, 2.1-2.5
Mon, Sep 12 co-NP, EXP, NEXP and the Time Hierarchy Theorem
Homework 1 | Cook-Levin Theorem (handy for homework)
Reading: Arora-Barak 1, 2.6, 3.1
Wed, Sep 14 PSPACE, NPSPACE, L, NL and Savitch's Theorem
Reading: Arora-Barak 4.1, 4.2
Mon, Sep 19 Hard Problems for PSPACE and NL
Reading: Arora-Barak 4.1-4.3; 6.5
Wed, Sep 21 The Immerman-Szelepcesnyi Theorem
Reading: Arora-Barak 4.4
Mon, Sep 26 A hard problem for EXPSPACE
Reading: The Reachability Problem Requires Exponential Space by Richard J. Lipton
Homework 2
Wed, Sep 28 Intro to Randomized Computation
Reading: Arora-Barak 7.1-7.4
Mon, Oct 3 Three Results about BPP
Reading: Arora-Barak 5.1, 6.2, 7.7, 7.8
Wed, Oct 5 Space Bounded Randomized Complexity Classes
Reading: Arora-Barak 7.10
Fri, Oct 7 Make-up Class: 3pm, Room ICCS X530
RLP; Interactive Proof Systems
Notes on RL and RLP
Reading: Arora-Barak 7.10; Arora-Barak 8.1, 8.2,8.3, 8.5
Mon, Oct 10 Holiday - Canadian Thanksgiving
Wed, Oct 12 TQBF is in IP
Homework 3
Mon, Oct 17 Anne away, class rescheduled on Fri Oct 7, 3pm
Wed, Oct 19 Anne away, class rescheduled on Fri Oct 21, 3pm
Fri, Oct 21 TQBF is in IP, Continued; Intro to Approximation Algorithms
Handout on IP=PSPACE
Mon, Oct 24 PCP and Hardness of Approximation
Handout on Hardness of Approximation
Reading: Arora-Barak, 18.1, 18.2
Wed, Oct 26 Proof of the weak PCP theorem
Homework 4
Information on Reading Project and Presentation
Mon, Oct 31 Introduction to Quantum Information
Wed, Nov 2 Superdense Coding and Quantum Circuits
Mon, Nov 7 BPP is contained in BQP and BQP is contained in PSPACE
Wed, Nov 9 Simon's Algorithm
Mon, Nov 14 Introduction to Models of Molecular Computation
Homework 5
Wed, Nov 16 Models of Molecular Computation, Continued
Mon, Nov 21 Anne away, class rescheduled for Mon Dec 5
Wed, Nov 23 Anne away, class rescheduled for Mon Dec 5
Mon, Nov 28 Stochastic CRN kinetics and expected runtimes
Wed, Nov 30 Square is not in Stable-CRN, and more
Mon, Dec 5 Reading Project Presentations, 12:30-3:30pm, Room X530