CSE 200, Computability and Complexity, Spring, 2007

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4248 Computer Science Building, EBU3b
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu


Class Times: M, W 5:00-6:20, EBU3b 2154
TA: Chris Calabro, ccalabro@cs.ucsd.edu
Office Hours: TBA

Announcements:
Course Handouts
  1. Class Description
  2. Calibration Homework, due April 11
    3. Lecture notes are by Chris Calabro, and are often Chris's way of presenting things not Russell's.
  3. First Lecture Notes: 1 tape vs multi-tape TMs.
  4. Lecture Notes: RAMs and circuits
  5. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT
  6. Recommended additional reading related to last three lectures: Chapter 7 and Chapter 9.