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:
- Turing machines
- NP and NP-completeness
- Diagonalization
- Space complexity
- The polynomial hierarchy
- Boolean circuits
- Randomized computation
- Interactive proofs
- The PCP Theorem
- 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
- Wednesday, Jan 3, 2024. First day of class. Introduction to
Turing machines.
- Monday, Jan 8, 2024. Proof of Universal Turing machine with
logarithmic overhead. Def DTIME, P. Undecidability of UC.
- Wednesday, Jan 10, 2024. Halting problem. Intro to
NP/NPcompleteness.
- Monday, Jan 15, 2024. NO CLASS (MLK Day)
- Wednesday, Jan 17, 2024. Cook-Levin Theorem.
- Monday, Jan 22, 2024: Ladner's Theorem. Deterministic time
hierarchy theorem.
- Wednesday, Jan 24, 2024: Remainder of Diagonalization chapter
(Non-deterministic time hierarchy Theorem and separation of P,NP
with respect to oracles).
- Monday, Jan 29, 2024: Beginning of Chapter 4 on space
complexity
- Wednesday, End of Chapter 4, beginning og Chapter 5 on the
polynomial hierarchy
- Monday, Feb 5, 2024. End of Chapter 5
- Wednesday, Feb 7, 2024. Beginning of Chapter 6 on circuits
- Monday, Feb 12, 2024. End of circuit chapter. Definition of
BPP.
- Wednesday, Feb 14, 2024. Continuation of Randomized Computing
chapter
- Monday, Feb 19, 2024. NO CLASS (Presidents Day)
- Wednesday, Feb 21, 2024. Thomas is travelling. Please the
remainder of Chapter 7 starting from Theorem 7.11 (ZEROP is in
coRP).
- Monday, Feb 26, 2024: Beginning of Chapter 8 (Interactive
proofs).
- Wednesday, Feb 28, 2024: Finished Chapter 8.
- Monday, Mar 4: The PCP Theorem
- 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.
You can check your points on the GradeScope
webpage.
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.