"Towards Hardness for the Minimum Circuit Size Problem"
Rahul Ilango (MIT)
Monday October 19 2-3pm
Abstract: While understanding the complexity of the Minimum Circuit Size Problem (MCSP) is strongly motivated by connections to areas like learning theory, average-case complexity, and circuit complexity, we still know relatively little about the problem. In particular, it is a longstanding open problem to base the intractability of MCSP on standard worst-case assumptions.
In this talk, I will survey a series of recent works that prove hardness results for natural variants of MCSP. This includes NP-hardness for an oracle-version, a multi-output version, and a constant-depth formula version. I'll discuss the last result in the most detail, and I'll highlight an application that uses similar techniques to prove the existence of functions with a 2^{\Omega_d(n^1/5)}-gap between their depth-d and depth-(d+1) formula complexity.