Completed
Is MCSP NP-hard?
Class Central Classrooms beta
YouTube videos 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
