MCS 541 - Computational Complexity
University of Illinois at Chicago
Spring 2023

This course will introduce students to the fundamental ideas underlying modern computational complexity. We will cover different computing models, time and space complexity of computations, and the classification of problems according to their computational complexity. Topics to be covered include completeness, the power of randomness, cryptography and one-way functions, interactive proof systems, relativization, and more.

Basic information

Syllabus: pdf
Time and location: M-W-F 1:00-1:50PM, 302 Addams Hall (AH)
Instructor information: Lev Reyzin, SEO 417
Textbook: Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach (see free online draft)
Optional textbook: Michael Sipser. Introduction to the Theory of Computation, 3rd Edition (earlier editions are also fine)
Office hours: T 9:00-9:50AM (online), F 9:00-9:50AM (in-person)
Piazza site: link

Exam dates

midterm exam: Friday March 17, 1:00-1:50PM
final exam: Monday May 1, 1:00-3:00PM

Problem sets

problem set 1, due 1/23/23
problem set 2, due 2/13/23
problem set 3, due 3/6/23
problem set 4, due 3/29/23
problem set 5, due 4/17/23
problem set 6, due 4/28/23

Lectures and readings

Lecture 1 (1/9/23)
covered material: automata (DFAs), regular languages
reading: chapter 0 of Arora-Barak
optional reading: chapter 1 of Sipser

Lecture 2 (1/11/23)
covered material: nondeterminism (NFAs), Turing Machines (TMs)
reading: chapters 1.1 and 1.2 of Arora-Barak
optional reading: chapter 3.1 of Sipser

Lecture 3 (1/13/23)
covered material: Church-Turing thesis, uncomputability, Turing reductions
reading: chapter 1.5 of Arora-Barak
optional reading: chapter 4 of Sipser

Lecture 4 (1/18/23)
covered material: universal TMs (UTMs), nondeterministic TMs (NTMs)
reading: chapter 1.4 of Arora-Barak
optional reading: chapter 3.2 of Sipser

Lecture 5 (1/20/23)
covered material: computable functions, DTIME, NTIME, P, NP
reading: chapters 1.3, 1.6, and 2.1 of Arora-Barak
optional reading: chapters 7.1 - 7.3 of Sipser

Lecture 6 (1/23/23)
covered material: Karp reductions, NP-Completeness
reading: chapter 2.2 of Arora-Barak
optional reading: chapter 7.4 up to Cook-Levin of Sipser

Lecture 7 (1/25/23)
covered material: Cook-Levin theorem
reading: chapter 2.3 of Arora-Barak
optional reading: chapter 7.4 starting from Cook-Levin of Sipser

Lecture 8 (1/27/23)
covered material: web of reductions, co-NP
reading: chapters 2.4 and 2.5 of Arora-Barak
optional reading: chapter 7.5 of Sipser

Lecture 9 (1/30/23)
covered material: EXP, NEXP, padding argument, space complexity, SPACE and NSPACE
reading: chapters 2.6 and 2.7 of Arora-Barak
optional reading: chapter 8.2 of Sipser

Lecture 10 (2/1/23)
covered material: bounding space by time, Time Hierarchy Theorem, Space Hierarchy Theorem
reading: chapter 3.1 of Arora-Barak
optional reading: chapter 9.1 of Sipser

Lecture 11 (2/3/23)
covered material: PSPACE, TQBF, sublinear space machines, L, NL
reading: chapter 4.1 of Arora-Barak

Lecture 12 (2/6/23)
covered material: TQBF is PSPACE-Complete, PSPACE = NPSPACE, Savich's Theorem
reading: chapter 4.2 of Arora-Barak
optional reading: chapter 8.1 of Sipser

Lecture 13 (2/8/23)
covered material: Ladner's Theorem
reading: chapter 3.3 of Arora-Barak

Lecture 14 (2/10/23)
covered material: P ≠ SPACE(n), PATH is NL-Complete
reading: chapter 4.3 (up to 4.3.1) of Arora-Barak
optional reading: chapter 8.5 of Sipser

Lecture 15 (2/13/23)
covered material: NL verifiers, the Immerman-Szelepcsenyi Theorem (NL = co-NL)
reading: finish chapter 4.3 of Arora-Barak
optional reading: chapater 8.6 of Sipser

Lecture 16 (2/15/23)
covered material: the Baker-Gill-Solovey relativization barrier
reading: chapter 3.4 of Arora-Barak
optional reading: chapter 9.2 of Sipser

Lecture 17 (2/17/23)
covered material: on the P vs NP problem, a talk by Avi Wigderson (asynchronous)
optional reading: section 2 of this paper by Avi Wigderson (IAS)

Lecture 18 (2/20/23)
covered material: the polynomial heirarchy (PH)
reading: chapters 5.1 and 5.2 of Arora-Barak
optional reading: chapter 10.3 of Sipser (for a definition of PH via alterinating TMs)

Lecture 19 (2/22/23)
covered material: deterministic interactive proofs
reading: chapter 8.1.1 of Arora-Barak

Lecture 20 (2/24/23)
covered material: probabilistic interactive proofs, IP
reading: chapter 8.1.2 and 8.1.3 of Arora-Barak

Lecture 21 (2/27/23)
covered material: IP ⊆ PSPACE, arithmetization, #SAT
reading: chapter 8.3.1 of Arora-Barak

Lecture 22 (3/1/23)
covered material: sumcheck protocol, linearization, IP = PSPACE
reading: chapter 8.3.2 and 8.3.3 of Arora-Barak
optional reading: chapter 10.4 of Sipser

Lecture 23 (3/3/23)
covered material: probabilistic TMs (PTMs), BPTIME, BPP, RTIME, RP, ZTIME, ZPP
reading: chapters 7.1 and 7.3 of Arora-Barak

Lecture 24 (3/6/23)
covered material: ZPP = RP ∩ co-RP, randomized median finding, biased coins for PTMs
reading: chapters 7.2 and 7.4 of Arora-Barak
optional reading: chapter 10.2 of Sipser

Lecture 25 (3/8/23)
covered material: Boolean circuits, SIZE, P/poly, P ⊊ P/poly, nonuniformity
reading: chapter 6.1 of Arora-Barak

Lecture 26 (3/10/23)
covered material: universality of exponential-size circuits, P-uniformity, TMs that take advice
reading: chapters 6.2 and 6.3 of Arora-Barak

Lecture 27 (3/13/23)
covered material: self-reducibility, Levin reductions, the Karp-Lipton Theorem
reading: chapter 6.4 of Arora-Barak

Lecture 28 (3/15/23)
covered material: circuit lower bounds, Nonuniform Hierarchy Theorem
reading: chapters 6.5 and 6.6 of Arora-Barak

Lecture 29 (3/17/23)
midterm exam: no lecture

Lecture 30 (3/27/23)
covered material: intro to cryptography, one-time pads
reading: chapter 9.1 of Arora-Barak

Lecture 31 (3/29/23)
covered material: perfect secrecy, computational security, negligible functions
reading: chapter 9.2 upto 9.2.1 of Arora-Barak

Lecture 32 (3/31/23)
covered material: one-way functions and their use in encryption
reading: chapters 9.2.1 and 9.2.2 of Arora-Barak

Lecture 33 (4/3/23)
covered material: pseudorandomness, unpredictablility, zero knowledge proof of graph isomorphism
reading: chapters 9.2.3 and 9.3.1 of Arora-Barak

Lecture 34 (4/5/23)
covered material: bit commitment, statistical (SZK) and computational (ZK) zero knowledge, NP ⊆ ZK
reading: chapters 9.4 and 9.5.3 of Arora-Barak

Lecture 35 (4/7/23)
covered material: hardness versus randomness, a talk by Avi Wigderson (asynchronous)
optional reading: chapter 20.1 of Arora-Barak

Lecture 36 (4/10/23)
covered material: machine learning, logic, and interpretability workshop
optional reading: Learnability can be independnet of set theory by Ben-David et al. (2021)

Lecture 37 (4/12/23)
covered material: machine learning, logic, and interpretability workshop, continued
optional reading: Using explainable boosting machines (EBMs) to detect common flaws in data by Chen et al. (2022)

Lecture 38 (4/14/23)
covered material: machine learning, logic, and interpretability workshop, final day
optional reading: Interpreting deep-learned error-correcting codes by Devroye et al. (2022)

Lecture 39 (4/17/23)
covered material: approximation algorithms for NP-Hard problems
reading: chapter 11.1 of Arora-Barak

Lecture 40 (4/19/23)
covered material: probabilistically checkable proofs, PCP theorem
reading: chapter 11.2 of Arora-Barak

Lecture 41 (4/21/23)
covered material: the two views of the PCP theorem, constraint satisfaction problems (CSPs)
reading: chapter 11.3 of Arora-Barak

Lecture 42 (4/24/23)
covered material: hardness of approximation for VC and IS from the PCP theorem
reading: chapter 11.4 of Arora-Barak

Lecture 43 (4/26/23)
covered material: the Walsh-Haddamard code, proof (of relaxed PCP theorem) that NP ⊆ PCP(poly(n), 1)
reading: chapter 11.5 of Arora-Barak

Lecture 44 (4/28/23)
covered material: review for final exam