Circuit Complexity from Circuit Analysis Algorithms

Speaker

Ryan Williams
CSAIL MIT

Host

Sam Hopkins
CSAIL MIT
Abstract: I will explain how I got into circuit complexity, and how I ended up proving theorems like "NEXP does not have small ACC circuits". (The answer may surprise you! Or maybe not.) I'll also talk about what else has been proved, building on the ideas that were introduced.