CSE 200, Computability and Complexity, Spring 2013

Professor Shachar Lovett

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)

Textbook:

Topics:

1. 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)
2. Universal machines and diagonalization: Undecidability. Recursive enumerability. The Halting Problem. Time and Space Hierarchy Theorems. Reductions. (Chapter 3).
3. NP-completeness and the P vs NP question. Consequences of P = NP. The polynomial-time hierarchy. (Chapters 2 and 5)
4. Space Complexity (Chapter 4)
5. Randomized computing (Chapter 7)
6. Time permitting: Interactive proofs (Chapter 8), Quantum computation (Chapter 10)

Homework:

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

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