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:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, 1st edition, 2009. Online version (draft).

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:


Classes and handouts: