CSE531 - Computational Complexity - Winter 2024

Course information

• Class schedule: MW 11:30 - 12:50 in ECE 026
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: We 2-3pm in CSE 556
  
• Course description: Computational complexity studies the question of what problems can be computed (at all) by an algorithm and if so what are the resources (usually running time) to do so. This course offers a rigorous mathematical introduction into the area. While complexity theory has existed for more than 50 years, many lower bounds remain unproven in the form of conjectures and much of complexity theory deals with showing implications between those conjectures as well as finding evidence for or against said conjectures. The preliminary plan is to cover the following chapters:
  
  1. Turing machines
  2. NP and NP-completeness
  3. Diagonalization
  4. Space complexity
  5. The polynomial hierarchy
  6. Boolean circuits
  7. Randomized computation
  8. Interactive proofs
  9. The PCP Theorem
  10. Circuit lower bounds
      
• Prerequisites: This is a proof-heavy graduate class. Formally CSE 311 is the requirement.
  
  
• Lecture notes: The course follows the textbook
  
  • Computational Complexity: A Modern Approach by Arora, Barak
  However, you may find lecture notes here which represent closely what is being covered in the course. For some of the covered proofs the notes give more details (while it skips the material that the course does not cover). Updates will be posted later. I would appreciate an email if you find a mistake/typo.
  
  
• Required Work:

• Your grade will be calculate as:
  
• 50%: Weekly homework assignments that will be submitted via GradeScope.
  
• 20%: Take home midterm
• 30%: In person final exam.
  
• Students are expected to read the lecture notes in parallel to the lecture.

• Final exam: Mar 13, 2:30pm-4:20pm in ECE 026 (in person!). Allowed is a print-out or electronic copy of the lecture notes.
  
• Collaboration policy: You may work with other students in finding solutions to homework problems, but please write up solutions on your own. For the take home mid term (as well as the in person final exam) no collaboration is allowed.
  
• Discussion forum: Other than in office hours, you may ask questions on course content and homework on the course discussion forum 

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).
    
17. Wednesday, Feb 28, 2024: Finished Chapter 8.
18. Monday, Mar 4: The PCP Theorem
19. Wednesday, Mar 4 (LAST CLASS): The PCP Theorem
    

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

Problem sets

• Homework 1, due Friday, Jan 12, 2024, 11pm on GradeScope.
• Homework 2, due Friday, Jan 19, 2024, 11pm on GradeScope.
• Homework 3, (UPDATED on Jan 20) due Friday, Jan 26, 2024, 11pm on GradeScope.
• Homework 4, (UPDATED on Jan 29; removed the word "unary" for Ex 3.8) due Friday, Feb 2, 2024, 11pm on GradeScope
• Homework 5, due Friday, Feb 16, 2024, 11pm on GradeScope.
• Homework 6, due Friday, Feb 23, 2024, 11pm on GradeScope.
• Homework 7, due Friday, Mar 1, 2024, 11pm on GradeScope.
• Homework 8, due Friday, Mar 8, 2024, 11pm on GradeScope.
  

Updates to the lecture notes

• Jan 10, 2024. Chapter 1: added a figure. Chapter 2: First z_{C,1} in NP-completeness of 3SAT should not be negated. Fixed a few typos.
• Jan 17, 2024. Chapter 2: replace "completeness" by "hardness" at beginning of the proof of Cook-Levin Theorem.
• Feb 1, 2024. Chapter 3: Changed the \not\subseteq to \subset in a few occurances. Chapter 4: Fixed indices in NL=coNL. Throughout the notes, I replaced quantor with quantifier
• Feb 2, 2024. Chapter 4: Sometimes SPACE was used instead of DSPACE and NPSPACE(S(n)) instead of NSPACE(S(n))
• Feb 12, 2024. Fixed a few typos in Chapters 5+6.
• Feb 26, 2024. Few fixes in Chapter 8. In SUMCHECK in IP Theorem statement we need a in Z_p^n and not a in {0,1}^n.  b -> b'.max -> min in def of L_i. O_t -> O_T. Added a footnote. Chapter 9. {0,1} -> {0,1}^n.