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 work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

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 determining the minimum size of a depth-$d$ formula computing a given Boolean function is NP-hard under quasipolynomial-time randomized reductions for all constant $d \geq 2$. Our approach is based on a method to "lift" depth-$d$ formula lower bounds to depth-$(d+1)$. This method also implies the existence of a function with a $2^{\Omega_d(n)}$ additive gap between its depth-$d$ and depth-$(d+1)$ formula complexity.

We also make 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,\star\}^*$) is not in P under the Exponential Time Hypothesis (ETH).

Intriguingly, we formulate a notion of lower bound statements being $(P/poly)$-recognizable that is closely related to Razborov and Rudich's definition of being $(P/poly)$-constructive. We show that unless there are subexponential-sized circuits computing SAT, the collection of lower bound statements used to prove the correctness of our reductions cannot be $(P/poly)$-recognizable.