Rahul Ilango, MIT
Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this talk, we will survey some of these connections and discuss recent progress towards showing MCSP is intractable under worst-case assumptions.
In particular, while Masek showed in the late 1970s that the version of MCSP for DNF formulas is NP-hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that the constant depth formula version of MCSP is NP-hard (under quasipolynomial-time reductions) for all constant depths. Our approach is based on a novel method to "lift" depth-d formula lower bounds to depth-(d+1). Intriguingly, this method also implies the existence of a function with a 2^{\Omega_d(n^{1/5})} additive gap between its depth-d and depth-(d+1) formula complexity.
We also discuss progress in the case of general, unrestricted circuits. We show that the version of MCSP where the input is a partial function (represented by a string in {0,1,?}*) is not in P under the Exponential Time Hypothesis (ETH).
Rahul Ilango is a second-year PhD student at MIT advised by Ryan Williams. He studies complexity theory and is particularly interested in the mysterious Minimum Circuit Size Problem.