The Constant Depth Formula and Partial Function Versions of MCSP are Hard

Explore the complexity of the Minimum Circuit Size Problem (MCSP) and its variants in this IEEE conference talk. Delve into the importance of MCSP, its potential NP-hardness, and its connections to circuit lower bounds. Examine the key ideas behind (Partial Function)-MCSP and (Depth-d Formula)-MCSP. Investigate the power of constant depth formulas and the impact of additional depth. Learn about the proof strategy and the reasoning behind the inductive step in this 23-minute presentation by MIT researcher Rahul Ilango.

Talk Outline
The Minimum Circuit Size Problem (MCSP)
Why care about MCSP?
Is MCSP NP-hard?
MCSP & New Kinds of Circuit Lower Bounds
(Partial Function)-MCSP
Key Ideas
(Depth-d Formula)-MCSP
Constant Depth Formulas
What is the power of extra depth (additively)?
Proof Strategy
Idea behind the inductive step