CS 354: Topics in Circuit Complexity, Spring 2016

Lecturer: Ryan Williams
Time: Friday 2:30-4:55pm, TBA
Office Hours: By appointment/email


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


Lectures (the rough plan)