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:

*Are algorithms that are given more time always able to solve more problems?**Is verifying solutions to problems easier than coming up with such solutions?**Can tossing coins help us compute faster?**can we define randomness?**Is finding approximate answers easier than finding exact answers?**Can we prove that some interesting problems cannot be solved efficiently?**Can you verify that an algorithm solves a problem without solving it yourself?*

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:

- Branching Programs
- Communication Complexity
- Lower bounds for linear/semidefinite programs
- Fine-grained complexity
- Algebraic Circuits & Formulas

**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

*Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach*

(online version here)

Any different resource used will be posted on this homepage.

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

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.

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

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 |