CMPT 407/710
Computational Complexity - Fall 2019
Announcements
- 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%
Teaching staff
Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011
TA: Sophie Oh (sophieo@sfu.ca).
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
Assignments
I'll post homework assignments & solutions.
- Homework 1 solutions
- solutions to Quiz 1
- Homework 2 solutions
- solutions to Quiz 2
- Homework 3 solutions
- solutions to Quiz 3
- Homework 4 solutions
- solutions to Quiz 4
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).
- 09/4: Lecture 1 (intro) Read: Chap. 0, Secs. 1.1-1.3 (Read ahead: Secs. 1.4-1.7.)
Slides for Lecture 1 (pdf) and Slides for Lecture 1 (one note)
- 09/6: Lecture 2: Turing machines.
Read: Secs. 1.1-1.3 (Read ahead: Secs. 1.4-1.7.)
Slides for Lecture 2 (pdf) and Slides for Lecture 2 (one note)
- 09/9: Lectures 3-4 : Universal Turing machines; Linear Speed-up Theorem. Read: Chap. 2. (Read ahead: Sec. 3.1.)
Slides for Lectures 3-4 (pdf) and Slides for Lectures 3-4 (one note)
- 09/11: Lecture 4: UTM (completed); Linear Speed-up Theorem.
- 09/13: Lectures 5-7
: Complexity Classes; reductions; Hierarchy theorems.
Read: Sec. 3.1, 3.3, 4.1.
Slides for Lectures 5-7 (pdf) and Slides for Lectures 5-7 (one note)
- 09/16: Lecture 6: NP. Between P and NP-complete (Ladner's theorem).
- 09/18:Lecture 7: Ladner's Theorem (concluded); Schaefer's Dichotomy Theorem.
- 09/20: Lecture 8: Circuits vs. Turing machines; P ⊆ P/poly. Read: Chap. 6.
- 09/23: Lecture 9: Complete problems for P and NP. Read: Chap. 6.
- 09/25: Lecture 10: Logspace reductions, the Size Hierarchy Theorem, SAT variants, co-NP, and NTime Hierarchy. slides (pdf) and (one note) Read: Chap 6, Sec. 2.3. (Read ahead: Sec. 3.2 and Chap. 5)
- 09/30: Lecture 11: Search-to-Decision, Universal SAT-algorithm, Polytime hierarchy. Read: Chap. 2, and Sec. 3.2. (Read ahead: Chap. 5.) slides (pdf) and (one note)
- 10/2: Lectures 12: Polynomial-Time Hierarchy, Time-Space Tradeoffs for SAT. Read: Secs. 5.3-5.5, 6.4. (Read ahead: 6.7, and Chap 7.)
- 10/4: Lecture 13: Inside PolySize: NC1, TC0, AC0 Read: Secs. 6.7, 14.1. (Read ahead: Chap 7.)
- 10/7: Lecture 14: NC1=Formulas, adding n n-bit numbers in NC1.
- 10/9: Lecture 15: PARITY ∉ AC0, the Switching Lemma.
- 10/11: Lecture 16: Parity ∉ AC0 (cont'd); matching upper bound.
- 10/16: Lectures 17: Randomized complexity classes. Read: Secs. 7.1-7.5.1.
- 10/21: Lectures 18: k-SAT randomized algorithm from the Switching Lemma.
- 10/23: Lecture 19: k-SAT randomized algorithm from the Switching Lemma (cont'd)
- 10/25: Lecture 20: BPP in PolySize, and BPP in PH; MA, AM, and IP; Graph Non-Isomorphism in IP.
- 10/28: Lecture 21: error reduction for MA; MA ⊆ AM; logical characterizations of MA and AM; AM ⊆ Π2p; 2-wise independent hash functions. Read: Secs. 8.1, 8.2. (Read ahead: Secs. 8.3-8.7.)
- 10/30: Lecture 22: Graph Non-Isomorphism in AM. Read: Secs. 8.1, 8.2. (Read ahead: Secs. 8.3-8.7.)
- 11/01: Lecture 23: Schwartz-Zippel Lemma & Polynomial Identity Testing. Read: Secs. 7.2.3, 8.2.4. (Read ahead: Secs. 8.3-8.7.)
- 11/04: Lecture 24: #SAT in IP, and IP=PSPACE. Read: Secs. 8.3, 8.5. (Read ahead: Chap. 11.)
- 11/06: Lecture 25: PCP Theorem and hardness of approximation. Read: Secs. 11.1-11.4 (Read ahead: Chap. 10.)
- 11/13: Lecture 26:
Hardness of approximation (concluded); Quantum computation.
Read: Secs. 10.1-10.3. (Read ahead: Secs. 10.4, 10.5, and 10.7.)
For a great introduction to Quantum Mechanics, watch this amazing lecture by Richard Feynman!
- 11/15: Lecture 27: Quantum computation: Definition of BQP; Elementary 1-qubit operations (NOT and Rotation); EPR paradox. (see the previous lecture notes and slides)
- 11/18: Lecture 28: Quantum computation: EPR paradox via XOR games; more quantum operations.
- 11/20: Lecture 29: BPP⊆ BQP, and Simon's algorithm. Read: Sec. 10.3. (Read ahead: Secs. 10.4, 10.5, and 10.7.)
- 11/22: Lecture 30: Simon's algorithm and Grover's Search algorithm. (see the previous lecture notes and slides)
- 11/25: Lecture 31 : SETH and OV; Barriers for ``P vs. NP'': Relativization. Read: Chap. 23. (Read ahead: Chap. 23)
- 11/27: Lecture 32 : Barriers for ``P vs. NP'': Algebrization and Natural Proofs. Five Worlds. Read: Chap. 23, Sec. 18.4.
Slides for lectures 8-10 on circuit complexity (pdf) and (one note)
Slides for Lectures 12 (pdf) and (one note)