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
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube