CS 278: Computational Complexity Theory (Fall 2025)
Course Information
Instructor: Lijie Chen
Email: lijiechen at berkeley dot edu
Office Hours: TBD
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
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
Course Topics
The course will cover the following major areas (to be finalized before the first class):
Time-Complexity (Chapter 3 AB)
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)
Randomness in Computation (Chapters 5,7 AB)
Hardness vs Randomness (Chapters 19, 20 AB)
Interactive Proofs (Chapter 8 AB)
PCP Theorem (Chapter 11 AB)
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
Class Syllabus (to be finalized before the first class)
Date |
Lecture |
08/28 Thu |
Course overview & Logistics |
Time complexity and relativization |
09/02 Tue |
Time complexity and Hierarchy theorems: Part I |
09/04 Thu |
Time complexity and Hierarchy theorems: Part II hw1 and project list out |
09/09 Tue |
Oracles and the Relativization Barrier: P vs NP |
Space complexity |
09/11 Thu |
Space complexity: Introduction and Savitch's Theorem (L vs NL) |
09/16 Tue |
Space complexity: NL = coNL |
09/18 Thu |
Time-T in square-root T space: the simulation |
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
HW1: Due September 26 (Thursday)
HW2: Due October 24 (Thursday)
HW3: Due November 20 (Thursday)
HW4: Due December 9 (Tuesday)
Course Policies
Additional Resources
|