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
|
|