CSE 200, Computability and Complexity, Winter, 2019

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:MWF, 3-4, WLH 2204
TA: Jiawei Gao
Russell's Office Hours: TTh, 3-4. 4248 CSE, or 4258 if it is crowded
Jiawei's Office Hours: M, W: 12-1. (tentative, TBA) Kenneth's Office Hours: T, Th: 12-1. (tentative, TBA)

Announcements:
Course Handouts

  1. READ THIS!!!!!!! Class Description
  2. Homework 1 due Jan. 14. See class description for guidelines
Lecture notes by Jiawei Gao, Fall, 2016, supplemented by older notes by Chris Calabro and William Matthews. We'll update these if there are significant changes this year.
  1. 1 tape vs multi-tape TMs.
  2. RAMs and circuits
  3. Simulating TMs by circuits
  4. Diagonalization
  5. Reductions
  6. Undecideability of tiling problems
  7. The class NP
  8. NP-completeness
  9. Lecture Notes: Search vs. Decision, and NP-Completeness of Circuit SAT (A bit redundant)
  10. NP-complete problems (I)
  11. NP-complete problems (II)
  12. Coping with NP-completeness, Polynomial hierarchy
  13. Chris's fanciful presentation (with more technical details) of the consequences of $P=NP$ to informal problems
  14. Polynomial hierarchy
  15. Space complexity
  16. >Space complexity: NL=co-NL
  17. Randomized algorithms and Probabilistic proofs (pdf)
  18. Probabilistic Algorithms: polynomial identity testing
  19. Probabilistic Algorithms: BPP
    Slides from class: TBA