Complexity Theory III

Explore advanced concepts in complexity theory through this 39-minute conference talk from STOC 2020. Delve into topics such as minimal circuits, the High Maintenance Theorem, probabilistic formulas, and subexponential formulas. Examine new developments in the field, including explicit obstructions and polynomials with high pockets. Gain insights into the coin problem and its implications for circuit complexity. Engage with thought-provoking questions and interpretations of recent results in this cutting-edge presentation from the Association for Computing Machinery (ACM).

Intro
Motivation Animation
Middle Circuits
New Development
Questions
Motivation
Minimal Circuit
High Maintenance Theorem
probabilistic formulas
subexponential formulas
interpreting the results
Explicit obstruction
Polynomials with the high pocket
The main lemma
The coin problem