CS 354: Topics in Circuit Complexity, Spring 2016
- Lecturer: Ryan Williams
- Time: Friday 2:30-4:55pm, TBA
- Office Hours: By appointment/email
Description:
One way to formally study the limitations and possibilities of computers is to analyze logical circuits as mathematical objects, and measure the complexity of a function by the necessary sizes and depths of circuits that can compute that function. The area of circuit complexity is rife with interesting and infamous mathematical problems concerning computational feasibility. In this course, we will study many fundamental results in circuit complexity, with a constant eye on how we can make new progress. For every topic we study, there will be a collection of open problems to consider.
Potential Topics:
The list may grow/shrink over time, depending on our progress.
- Small-size circuits
- Shannon-Lupanov bounds (counting arguments)
- Circuit size hierarchies
- Meyer-Stockmeyer's concrete lower bounds
- The gate elimination method: Linear-size lower bounds
- P/poly and its relation to the rest of complexity theory
- Kannan's fixed-polynomial size lower bound
- Depth-restricted circuits
- Boolean formulas and log-depth circuits
- Quadratic-size formula lower bounds
- Andreev's function and cubic-size formulas
- Representing circuits with polynomials 1: PARITY is not in $AC0$, MOD$p$ versus $AC0[q]$
- Representing circuits with polynomials 2: $ACC$
- More recently
- Learning $SAT$ circuits with an $NP$ oracle
- Circuit-$SAT$ Algorithms and Circuit Lower Bounds
- Circuit Satisfiability Algorithms
Assignments: There will be a final project (on some topic related to complexity) and occasional problem sets to keep you thinking about the material.
Prerequisites: This is an advanced graduate course, but open to anyone. You should know much of the material covered in CS 254 (Computational Complexity) and/or have "mathematical maturity" -- otherwise, the course may be tough to follow in some places. But I will recall the concepts needed along the way. Many students have taken 354 without 254 and done well.
If you haven't yet taken 254, and are interested in 354:
Read the first six chapters of Arora and Barak and you'll be ready.
The book is available online freely to Stanford students,
here.
There is no required textbook. I will post lecture notes as the course goes on.
Announcements:
Lectures (the rough plan)
- Week 1 Overview of Circuit Complexity [pdf]
- Week 2 Really Hard Functions + Arithmetic Circuits (coming soon...)
- Week 3 P/poly and Some Homework Problems [pdf]
- Week 4 Gate Elimination (coming soon...)
- Week 5 Circuit Size and Circuit Depth
- Week 6 Formulas
- Week 7 Constant-Depth Circuits with Threshold Gates
- Week 8 Constant-Depth Circuits with OR/AND/NOT
- Week 9 Constant-Depth Circuits with MOD Gates
- Week 10: Barriers in Complexity/Project Presentations/Brainstorming???