CS 278
Home
Project
Course Policy

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]
Reading: Section 3.1 of Ryan's paper
09/23 Tue Time-T in square-root T space: the Cook-Mertz algorithm
Reading: The Cook-Mertz paper and Notes by Oded
09/25 Thu Space complexity: a bit more on catalytic space algorithm
Reading: Theorem 3 of For TC1 in CL and Section 1.4 of For reachability in CL
Circuit Complexity
09/30 Tue Story of Circuit Lower Bounds: An Overview
Reading: Chapter 6&14 of Arora-Barak
10/02 Thu The natural proof barrier
Reading: Chapter 23 of Arora-Barak
10/07 Tue Algorithmic Approach 1: Ryan's algorithmic approach
Reading: Ryan's exposition: https://arxiv.org/abs/1111.1261, Roei's exposition
10/09 Thu Algorithmic Approach 2: Range avoidance
Reading: https://hanlin-ren.github.io/files/pdf/CHLR_S2E_journal.pdf
Randomized Complexity and Derandomization
10/14 Tue Randomized complexity and derandomization: an overview
10/16 Thu NW PRG and derandomization from circuit lower bounds
10/21 Tue Derandomization from uniform hardness, Part (1)
10/23 Thu Derandomization from uniform hardness, Part (2)
10/28 Tue Construction of Primes
Interactive Proofs and PCP Theorem
10/30 Thu IP = PSPACE
11/04 Tue PCP Theorem: a baby version
Meta complexity and Bounded arithmetic
11/06 Thu Meta-complexity: an overview
11/11 Tue Academic and Administrative Holiday
11/13 Thu Bounded Arithmetic: an overview
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 (Friday) hw1 hints

  • HW2: Due October 24 (Thursday) hw2 latex-template

  • 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