CSE531 - Computational Complexity - Winter 2024

Course information

Covered material

  1. Wednesday, Jan 3, 2024. First day of class. Introduction to Turing machines.
  2. Monday, Jan 8, 2024. Proof of Universal Turing machine with logarithmic overhead. Def DTIME, P. Undecidability of UC.
  3. Wednesday, Jan 10, 2024. Halting problem. Intro to NP/NPcompleteness.
  4. Monday, Jan 15, 2024. NO CLASS (MLK Day)
  5. Wednesday, Jan 17, 2024. Cook-Levin Theorem.
  6. Monday, Jan 22, 2024: Ladner's Theorem. Deterministic time hierarchy theorem.
  7. Wednesday, Jan 24, 2024: Remainder of Diagonalization chapter (Non-deterministic time hierarchy Theorem and separation of P,NP with respect to oracles).
  8. Monday, Jan 29, 2024: Beginning of Chapter 4 on space complexity
  9. Wednesday, End of Chapter 4, beginning og Chapter 5 on the polynomial hierarchy
  10. Monday, Feb 5, 2024. End of Chapter 5
  11. Wednesday, Feb 7, 2024. Beginning of Chapter 6 on circuits
  12. Monday, Feb 12, 2024. End of circuit chapter. Definition of BPP.
  13. Wednesday, Feb 14, 2024. Continuation of Randomized Computing chapter
  14. Monday, Feb 19, 2024. NO CLASS (Presidents Day)
  15. Wednesday, Feb 21, 2024. Thomas is travelling. Please the remainder of Chapter 7 starting from Theorem 7.11 (ZEROP is in coRP). 
  16. Monday, Feb 26, 2024: Beginning of Chapter 8 (Interactive proofs).

Last day of class will be Friday, Mar 8, 2024.

Problem sets

 You can check your points on the GradeScope webpage.

Updates to the lecture notes