CS 278 Computational Complexity Theory
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. The course will be based on selected chapters from the book “Computational Complexity” by Sanjeev Arora and Boaz Barak.
Among the highlights, we will discuss Randomized Algorithms, Bounded-Space Algorithms, Savitch's Theorem, Immerman-Szelepcsényi's Theorem, the PCP Theorem and its connections to Hardness of Approximation, Interactive Proofs and IP = PSPACE, Hardness vs. Randomness, Pseudorandomness and Derandomization, Hardness Amplification, Introduction to Communication Complexity, Karchmer-Wigderson games, Circuit Complexity, Hardness within P.
Time and Place: Tuesday, Thursday 2:00-3:30 PM (via Zoom)
Instructor: Avishay Tal, atal "at" berkeley.edu
Office Hours: Monday 4:00-5:00 PM
TA: Nagaganesh Jaladanki, nagaganesh "at" berkeley.edu
Grading: Homework assignments - 50% (5 assignments), scribe - mandatory + replaces the lowest-grade hw assignment, Final Project & Presentation - 50%. Participation in class - extra credit.
Prereqs: CS170 or equivalent is required. CS172 or equivalent is recommended.
For those of you that want a refresher on the general setting, or those that haven't took 172, please see Chapter 3 in Sipser's book ("Introduction to the Theory Of Computation" by Michael Sipser) or chapters 1 & 2 Arora-Barak.
Textbooks & Lecture Notes:
Oded Goldreich - Computational Complexity, A Conceptual Perspective
Avi Wigderson - Mathematics and Computation
Homework 1 - Due Thursday, Feb 11.
Homework 2 - Due Monday, Mar 1.
Homework 3 - Due Thursday, Mar 18.
Homework 4 - Due Friday, Apr 16.
Time-Complexity (Chapter 3 AB)
Barriers to diagonalization
Space-Complexity (Chapter 4 AB)
st-conn is NL complete
Savitch’s Theorem (NSPACE[s] in DSPACE[s^2])
Immerman-Szelepcsényi's Theorem (NSPACE is closed to complement)
Randomness in Computation (Chapters 5,7 AB)
Relation to the Polynomial Hierarchy
Relation to Circuits
Circuit Complexity (Chapters 6, 14, 23 AB)
The circuit complexity approach to P!=NP
The Karp-Lipton Theorem
Uncoditional lower bounds for restrictive circuit classes like bounded-depth circuits
NEXP not in ACC^0
Barriers: Natural Proofs.
Hardness vs Randomness (Chapters 19, 20 AB)
Pseudorandom Generators from Hard functions
Derandomization implies Circuit Lower Bounds
Interactive Proofs (Chapter 8 AB)
IP = PSPACE
The PCP theorem and its connections to Hardness of Approximation (Chapter 11 AB)