The Constant Depth Formula and Partial Function Versions of MCSP are Hard
Offered By: IEEE via YouTube
Course Description
Overview
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.
Syllabus
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
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Computational Complexity TheoryIndian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Quantum Complexity - Quantum Computation at CMU
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube