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 discuss recent work that proves 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 establish the existence of functions with a $2^{\Omega_d(n)}$ additive gap between their depth-$d$ and depth-$(d+1)$ formula complexity.