CS 278
Home
Project

CS 278: Computational Complexity Theory (Fall 2025)

Course Information

  • Instructor: Lijie Chen

  • Email: lijiechen at berkeley dot edu

  • Office Hours: Tuesday, 2:00 PM to 3:00 PM and Thursday, 11:00 AM to 12:00 PM, SODA 627

  • Reader: Carl Sun

  • Reader Email: carlsxh at berkeley dot edu

  • Time: Tuesday, Thursday 12:30 - 2:00 PM (we will be on Berkeley time, so 12:40 :) )

  • Location: Etcheverry 3113 map

  • Discord: https:discord.gg/U3965mgE2p

Course Description

Computational Complexity studies the power and limitations of efficient computation. What can be computed with bounded resources such as time, memory, randomness, communication, and parallel cores? In this course, we will explore these beautiful questions. While most of them are widely open (e.g., Is verifying easier than proving? Is parallelism always helpful? Does randomness help in computation?), we will see many surprising connections between them.

Besides covering classic works in the field such as the PCP Theorem and its connections to Hardness of Approximation, Interactive Proofs and IP = PSPACE, Hardness vs. Randomness, Pseudorandomness and Derandomization, we will also cover some recent results in the field, including Simulating Time With Square-Root Space and Cook and Mertz's Tree Evaluation algorithm, New Maximum Circuit Lower Bounds by Interesting Algorithms. We will also explore some connections between complexity theory and modern machine learning architectures.

Prerequisites

  • Required: CS 170 or equivalent

  • Recommended: CS 172 or equivalent

Course Topics

The course will cover the following major areas (to be finalized before the first class):

Time-Complexity (Chapter 3 AB)

  • Hierarchy Theorems

  • Barriers to diagonalization

Space-Complexity

  • PSPACE, LOGSPACE, space hierarchy theorems (Chapter 4 AB)

  • Savitch’s Theorem (NSPACEs in DSPACEs^2) (Chapter 4 AB)

  • Tree evaluation in log space (paper)

  • T-time in square root space (paper)

Circuit Complexity (Chapters 6, 14, 23 AB)

  • The circuit complexity approach to P!=NP

  • Circuit complexity lower bound via solving range avoidance (paper)

Randomness in Computation (Chapters 5,7 AB)

  • BPP, RP, ZPP, derandomization

Hardness vs Randomness (Chapters 19, 20 AB)

  • Pseudorandom generators, hardness amplification

Interactive Proofs (Chapter 8 AB)

  • IP = PSPACE, zero-knowledge proofs

PCP Theorem (Chapter 11 AB)

  • Probabilistically checkable proofs and approximation hardness

Complexity Theory for Modern Machine Learning Architecture (TBD)

  • The complexity of Transformer

  • The complexity of Chain-of-Thought

  • Encoders vs. Decoders

  • The complexity of Diffusion LLMs

Textbooks

Primary References

  • Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press

  • Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press

  • Avi Wigderson, Mathematics and Computation, Princeton University Press

Recommended Pre-Reading

  • Chapter 3 in Sipser's Introduction to the Theory of Computation

  • Chapters 1 & 2 in Arora-Barak

Class Syllabus (to be finalized before the first class)

Date Lecture
08/28 Thu Course overview & Logistics [slides]
Time complexity and relativization
09/02 Tue Time complexity and Hierarchy theorems: Part I [slides] [notes]
09/04 Thu Time complexity and Hierarchy theorems: Part II [slides] [notes] hw1 and project list out
09/09 Tue Time-space lower bounds for SAT. [slides]
Space complexity
09/11 Thu Space complexity: Introduction and Savitch's Theorem (L vs NL). [slides]
09/16 Tue Space complexity: NL = coNL [slides] Reading: Section 4.3 ("NL-completeness") from Arora-Barak
09/18 Thu Time-T in square-root T space: the simulation [slides]
09/23 Tue Time-T in square-root T space: the Cook-Mertz algorithm
09/25 Thu Space complexity: a bit more on catalytic space algorithm
Circuit Complexity
09/30 Tue Circuit complexity: Introduction
10/02 Thu Circuit complexity: Parity not in AC0
10/07 Tue Circuit complexity: The Natural Proof Barrier
10/09 Thu Circuit complexity: Range Avoidance
Randomized Complexity and Derandomization
10/14 Tue Randomized Complexity: Introduction
10/16 Thu Randomized Complexity: BPP, ZPP, RP, etc.
10/21 Tue Derandomization: P vs BPP, CAPP, Pseudorandom generators
10/23 Thu Derandomization: Pseudorandom generators from hard functions
Interactive Proofs and PCP Theorem
10/28 Tue Interactive Proof and PCP Theorems
10/30 Thu Interactive Proof and PCP Theorems: IP = PSPACE
11/04 Tue Interactive Proof: GKR protocol
Derandomization: Part II
11/06 Thu Derandomization: Derandomization via GKR protocol
11/11 Tue Academic and Administrative Holiday
11/13 Thu Derandomization: Construction of Primes
Complexity Theory for Modern Machine Learning Architecture
11/18 Tue The complexity of Transformer, State-space-model
11/20 Thu The complexity of Chain-of-thought and test-time-inference
11/25 Tue Lower Bounds against multi-layer transformers
11/27 Thu Thanksgiving
Presentations
12/02 Tue Project Presentation
12/04 Thu Project Presentation

Grading

  • Homework Assignments: 50% (4 assignments total)

  • Final Project & Presentation: 50% see project page for details.

    • Project presentations will be scheduled during the final weeks of the semester.

    • Project report deadline is December 10 6pm PT

Homework Assignments

  • HW1: Due September 26 (Thursday) hw1

  • HW2: Due October 24 (Thursday)

  • HW3: Due November 20 (Thursday)

  • HW4: Due December 9 (Tuesday)

Course Policies

  • Late Policy:

    • Late homework submissions will be penalized. Please contact the instructor in advance if you anticipate difficulties meeting deadlines.

Additional Resources