Completed
MCSP & New Kinds of Circuit Lower Bounds
Class Central Classrooms beta
YouTube playlists curated by Class Central.
Classroom Contents
The Constant Depth Formula and Partial Function Versions of MCSP are Hard
Automatically move to the next video in the Classroom when playback concludes
- 1 Talk Outline
- 2 The Minimum Circuit Size Problem (MCSP)
- 3 Why care about MCSP?
- 4 Is MCSP NP-hard?
- 5 MCSP & New Kinds of Circuit Lower Bounds
- 6 (Partial Function)-MCSP
- 7 Key Ideas
- 8 (Depth-d Formula)-MCSP
- 9 Constant Depth Formulas
- 10 What is the power of extra depth (additively)?
- 11 Proof Strategy
- 12 Idea behind the inductive step
