The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications on longstanding open problems. In a recent development, Golovnev et al. [11] improves the status of unconditional lower bounds for MCSP, showing that MCSP is not in $AC^0[p]$ for any prime $p$. While their results generalize to most "typical" circuit classes, it fails to generalize to the circuit minimization problem for depth-d formulas, denoted ($AC^0_d$)-MCSP. In particular, their result relies on a Lipchitz hypothesis that is unknown (and possibly false) in the case of ($AC^0_d$)-MCSP. Despite this, we show that ($AC^0_d$)-MCSP is not in $AC^0[p]$ by proving even the failure of the Lipchitzness for $AC^0_d$ formulas implies that MAJORITY reduces to ($AC^0_d$)-MCSP under $AC^0$ truth table reductions. Somewhat remarkably, our proof (in the case of non-Lipchitzness) uses completely different techniques than [11]. To our knowledge, this is the first MCSP reduction that uses modular properties of a function's circuit complexity.
We also define MOCSP, an oracle version of MCSP that takes as input a Boolean function $f$, a size threshold $s$, and oracle Boolean functions $f_1, ..., f_t$, and determines whether there is an oracle circuit of size at most $s$ that computes $f$ when given access to $f_1, ... , f_t$. We prove that MOCSP is $NP$-complete under non-uniform $AC^0$ many-one reductions as well as (uniform) $ZPP$ truth table reductions. We also observe that improving this $ZPP$ reduction to a deterministic polynomial-time reduction requires showing $EXP \neq ZPP$ (using theorems of Hitchcock and Pavan [17] and Murray and Williams [22]). Optimistically, these MOCSP results could be a first step towards $NP$-hardness results for MCSP. At the very least, we believe MOCSP clarifies the barriers towards proving hardness for MCSP and provides a useful "testing ground" for questions about MCSP.
