CSE 200, Computability and Complexity, Spring 2013
Office hours: Tuesday 1:00-2:00pm, Computer Science Building (EBU3b), room 4234
TA: Dongcai Shen
Office hours: Monday 2:00-3:00pm, Computer Science Building (EBU3b), room 3109
Class Times: M 12:30-13:50, W 2:00-3:20 , Computer Science Building (EBU3b), room 2154
Moodle (forum for Q/A)
Textbook: Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, 1st edition, 2009.
Online version (draft).
- Models of computation: Turing Machines and variants, RAM model, Boolean circuits. Simulating one machine model with another. The Church-Turing thesis and versions for efficient computation (Chapters 1, 3, and 6)
- Universal machines and diagonalization: Undecidability. Recursive enumerability. The Halting Problem. Time and Space Hierarchy Theorems. Reductions. (Chapter 3).
- NP-completeness and the P vs NP question. Consequences of P = NP. The polynomial-time hierarchy. (Chapters 2 and 5)
- Space Complexity (Chapter 4)
- Randomized computing (Chapter 7)
- Time permitting: Interactive proofs (Chapter 8), Quantum computation (Chapter 10)
Classes and handouts:
- [Class description, material, grading, etc]
- 4/1/2013: Introduction. Turing machines. Computable functions and robustness under different models.
(Arora-Barak 1-1.3) [notes]
- 4/3/2013: Universal Turing machines. Uncomputable functions. Definition of time complexity. (Arora-Barak 1.4-1.6).
- 4/8/2013: Time and space complexity and hierarchy theorems. (Arora-Barak 3.1 and 4.1).
- 4/10/2013: NP and NP-completeness. (Arora-Barak 2.1-2.2, 2.5).
- 4/15/2013: NP-completeness: Cook-Levin theorem. (Arora-Barak 2.3).
- 4/17/2013: Beyond NP: the Polynomial Hierarchy. (Arora-Barak 2.6, 5.1-5.2).
- 4/22/2013: Space complexity: Logspace computation. NL completeness. (Arora-Barak 4.1).
- 4/24/2013: Space complexity: PSPACE completeness. Savitch theorem. (Arora-Barak 4.2-4.3).
- 4/29/2013: Space complexity: NL=coNL. Boolean circuits. (Arora-Barak 4.3, 6.1-6.2).
- 5/1/2013: Boolean circuits: Karp-Lipton, Meyer theorems. (Arora-Barak 6.3-6.5).
- 5/6/2013: Boolean circuits lower bounds: PARITY is not in AC0 (see Arora-Barak 14.1 for a different proof).
- 5/8/2013: Boolean circuits lower bounds: PARITY is not in AC0 (contd), Natural proofs (Arora-Barak 23).
- 5/13/2013: Randomness in computation (Arora-Barak 7.1).
- 5/15/2013: Randomness in computation (Arora-Barak 7.2-7.4).
- 5/20/2013: Randomness in computation (Arora-Barak 7.5).
- 5/22/2013: Interactive proofs (Arora-Barak 8.1-8.2).