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.