Email: slovett@cs.ucsd.edu

Office hours: Tuesday 1:00-2:00pm, Computer Science Building (EBU3b), room 4234

TA: Dongcai Shen

Email: doshen@cs.ucsd.edu

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)

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

- Homework 1 (due 4/24/2013) [solution]
- Homework 2 (due 5/13/2013) [solution]
- Homework 3 (due 5/29/2013)
- Final exam (due 6/14/2013)

- [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). [notes]
- 4/8/2013: Time and space complexity and hierarchy theorems. (Arora-Barak 3.1 and 4.1). [notes]
- 4/10/2013: NP and NP-completeness. (Arora-Barak 2.1-2.2, 2.5). [notes]
- 4/15/2013: NP-completeness: Cook-Levin theorem. (Arora-Barak 2.3). [notes]
- 4/17/2013: Beyond NP: the Polynomial Hierarchy. (Arora-Barak 2.6, 5.1-5.2). [notes]
- 4/22/2013: Space complexity: Logspace computation. NL completeness. (Arora-Barak 4.1). [notes]
- 4/24/2013: Space complexity: PSPACE completeness. Savitch theorem. (Arora-Barak 4.2-4.3). [notes]
- 4/29/2013: Space complexity: NL=coNL. Boolean circuits. (Arora-Barak 4.3, 6.1-6.2). [notes]
- 5/1/2013: Boolean circuits: Karp-Lipton, Meyer theorems. (Arora-Barak 6.3-6.5). [notes]
- 5/6/2013: Boolean circuits lower bounds: PARITY is not in AC0 (see Arora-Barak 14.1 for a different proof). [notes]
- 5/8/2013: Boolean circuits lower bounds: PARITY is not in AC0 (contd), Natural proofs (Arora-Barak 23). [notes]
- 5/13/2013: Randomness in computation (Arora-Barak 7.1). [notes]
- 5/15/2013: Randomness in computation (Arora-Barak 7.2-7.4). [notes]
- 5/20/2013: Randomness in computation (Arora-Barak 7.5). [notes]
- 5/22/2013: Interactive proofs (Arora-Barak 8.1-8.2).