CS 278 Complexity Theory


This is a graduate course in computational complexity, including a mix of “classical” results, and a few very recent results from the last decade.

Complexity theory deals with the power of efficient computation. Here `efficiency’ could refer to any of the computational resources such as time, memory, communication, number of rounds of communication, and randomness.

While in the last century logicians and computer scientists developed a pretty good understanding of the power of finite time algorithms (where finite can be an algorithm that on on a 1000 bit input will take longer to run than the lifetime of the sun) our understanding of efficient algorithms is quite poor. Thus, complexity theory contains more questions, and relationships between questions, than actual answers. Nevertheless, we will learn about some fascinating insights, connections, and even few answers, that emerged from complexity theory research.

Complexity theory concerns itself with fundamental questions such as:

Apart from these general themes, this offering will have a special emphasis on concrete lower bounds for specific computational models. In particular, the course will explore at least a few of the following topics:

Logistics

Meeting Time: Monday-Wednesday 10:30-12:00pm
Room: 380 SODA
Office Hours: Monday 1:30-2:30 at 623 SODA (or by appointment)
Piazza: piazza page

Resources: A major portion of the course will use chapters from

Grading: 50% Homeworks + 25% Final + 25% Class Participation

Homeworks

There will be a short homework consisting of 1-2 problems assigned every week. The homework is due on Thursday by 5pm.

Please email your solutions to prasad@cs.berkeley.edu with Subj: “278 Homework #number” OR drop them in the mail box by the door at 623 Soda.

You are encouraged to discuss the problems and solve them in groups. However, the solutions are to be written up alone, listing all the collaborators.

Finals

There will be one take-home final at the end of the semester.

Lectures

Date Topic Resources
Aug 24 Introduction,Turing Machines, Diagonalization Sections 1.1, 1.2, 1.3, 1.4, 1.5.1 & 3.1
Aug 29 Nondeterminism, Cook's Theorem, NP-completeness, Definition of Polynomial Hierarchy Chapter 2
Aug 31 PSPACE, PSPACE-completeness of TQBF, Definition of NL/coNL Sections 4.1,4.2, Theorem 4.11
Sept 7 BPP Section 7.1, 7.2, Lemma 7.9, Section 7.6
Sept 12 NL-completeness, Savitch's Theorem, NL=coNL, Section 4.3.1, 4.4
Sept 14 Interactive Proofs Section 8.1,8.2,8.3,8.4.1
Sept 19 coNP in IP Section 8.5.1,8.5.2
Sept 21 PSPACE in IP Section 8.5.3
Sept 26 Cryptography Section 10.1, 10.2
Sept 28 Goldreich-Levin algorithm for learning linear functions section 10.3
Oct 3 PRG from one-way permutation, commitments, zero-knowledge proofs
Oct 5 PCP Theorem and hardness of approximation Section 18.1,18.2
Oct 10 Exponential sized PCP Section 18.4.1,18.4.2
Oct 12 Non-uniform Models of Computation - Circuits,Branching Programs, Formulas Lecture notes by Madhu Sudan
Oct 17 Razborov-Smolensky's ACC lower bound Lecture notes by Madhu Sudan
Oct 19 Formulas size lower bound for Element Distinctness Lecture notes by Madhu Sudan
Oct 24 Communication Complexity -- Karchmer-Wigderson Games, Protocols and Rectangles, Fooling Set Lecture Notes by Mark Braverman
Sec 2.2 in Lecture Notes by Prahladh Harsha
Oct 26 Randomized Communication Complexity, Min-Max, Discrepancy, Inner product function Lecture Notes by Prahlad Harsha
Oct 31 Applications of Communication Complexity: Streaming lower bounds, Monotone Depth Section 2.2.1 in lecture notes by Prahlad Harsha
Section 5.1 in lecture notes by Prahlad Harsha
Nov 2 Basics of Information Theory lecture1
lecture 2 by Mark Braverman
Nov 7 Communication Lower Bound for Disjointness Lecture Notes by Prahladh Harsha (Sec 11.2)
Nov 9 Proof Complexity Lecture Notes by Paul Beame and Ashish Sabharwal (Sec 1.1, 1.2, 2.1)
Introduction to sum-of-squares proof system in paper by O'Donnell and Zhou
Nov 14 Time-Bounded Derandomization Lecture notes by Dieter Van Melkebeek
Nov 16 Expanders Chapter 4 in Salil Vadhan's monograph
Nov 21 Space-Bounded Derandomization Lecture notes by Dieter Van Melkebeek
Nov 28 Relativization and Natural Proofs Chapter 22
Nov 30 Fine-Grained Complexity within P Survey by Virginia V. Williams