Complexity of Computation: CPSC506
2020 Winter Term 2


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

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

Resources

Piazza: Please register yourself. You will need an access code which will be announced in the initial classes. Any resources which can't be published publicly will be placed here. You can also ose Piazza for communication with peers and instructor about homeworks, projects, etc.

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 (see also Piazza)

Quantum Information and Quantum Computing
Lecture Notes by John Watrous

Theory of Molecular Computing
Lecture Notes by Dave Doty

Course Schedule (Lecture materials will be posted after class)

Date Resources
Mon, Jan 6 Course Overview and Pre-req Review; Intro to Wang Tiling
Reading: Arora-Barak 1, 2.1-2.5; Moore Section 7.6.5
Wed, Jan 8 Wang Tiling Completed; More complexity classes: co-NP, EXP, NEXP
Reading: Arora-Barak 1, 2.6
Dave Doty on algorithmic molecular self-assembly (interview, survey paper, video)
Mon, Jan 13 Time Hierarchy Theorem
Reading: Arora-Barak, 3.1; Time Hierarchy Theorem Handout
Homework 1 | Cook-Levin Theorem (handy for homework)
Wed, Jan 15 Snow Day!
Mon, Jan 20 Space Bounded Complexity Classes
Reading: Arora-Barak 4.1, 4.2
Wed, Jan 22 Space Bounded Complexity Classes Continued: Log Space
Reading: Arora-Barak 4.1-4.3
Mon, Jan 27 The Immerman-Szelepcesnyi Theorem
Reading: Arora-Barak 4.4
Homework 2
Wed, Jan 29 Intro to Randomized Computation
Reading: Arora-Barak 7.1-7.4
Hastad's notes have a nice discussion of polynomial identity testing.
Mon, Feb 3 Three Results about BPP
Reading: Arora-Barak 5.1, 6.2, 7.7, 7.8
Wed, Feb 5 BPP Completed; Space Bounded Randomized Complexity Classes
Reading: Arora-Barak 7.10
Mon, Feb 10 Space Bounded Randomized Complexity Classes
Reading: Arora-Barak 7.10
Notes on RL and RLP
Wed, Feb 12 Interactive Proof Systems
Arora-Barak 8.1, 8.2,8.3, 8.5
Homework 3
Mon, Feb 24 Interactive Proof Systems, Continued
Arora-Barak 8.1, 8.2,8.3, 8.5
Handout on Interactive Proof Systems
Wed, Feb 26 Approximation Algorthms and Probabilistically Checkable Proofs (PCPs)
Reading: Arora-Barak, 18.1, 18.2
Handout on PCPs
Homework 4
Mon, Mar 2 NP = PCP(poly(n),1)
Arora-Barak 8.4
Wed, Mar 4 NP = PCP(poly(n),1) Completed, Hardness of Approximating Clique
Information on Reading Project and Presentation
Mon, Mar 9 Introduction to Quantum Computing
Reading: John Watrous' Lecture Notes, Lectures 1,2,3
Wed, Mar 11 Quantum Circuits
Reading: John Watrous' Lecture Notes, Lectures 3,7
Mon, Mar 16 BPP is contained in BQP and BQP is contained in PSPACE
Link to compressed video (zip format)
(Video is also available for viewing on Skype.)
White Board Notes (1)
White Board Notes (2)
Homework 5
Wed, Mar 18 Simon's Algorithm
Mon, Mar 23 Molecular Programming Models
See Lecture Notes by Dave Doty
Wed, Mar 25 Stable Computation by Chemical Reaction Networks
Mon, Mar 30 Chemical Reaction Networks: Time Complexity
Wed, Apr 1 Chemical Reaction Networks Wrap-Up: Register Machine Simulation, Pumping Lemma
Mon, Apr 6 No class: Arrange time to discuss reading project instead
Wed, Apr 8 No class: Arrange time to discuss reading project instead
Tue, Apr 14 Reading Project Presentations: 9-10:30am