The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models.

Specifically, we show that computing MCSP, on functions with a truth table of length $N$, requires

$N^{3-o(1)}$-size de Morgan formulas, improving the recent $N^{2-o(1)}$ lower bound by Hirahara and Santhanam (CCC, 2017),
$N^{2-o(1)}$-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and
$2^{\Omega\left(N^{1/(d+2.01)}\right)}$-size depth-$d$ $AC^0$ circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006).

The $AC^0$ lower bound stated above matches the best-known $AC^0$ lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth-$2$ circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of \(2^{N^{1-o(1)}}\) for MCSP.

Some journal-version updates.

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models.

Specifically, we show that computing MCSP, on functions with a truth table of length $N$, requires

$N^{3-o(1)}$-size de Morgan formulas, improving the recent $N^{2-o(1)}$ lower bound by Hirahara and Santhanam (CCC, 2017),
$N^{2-o(1)}$-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and
$2^{\Omega\left(N^{1/(d+2.01)}\right)}$-size depth-$d$ $AC^0$ circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006).

The $AC^0$ lower bound stated above matches the best-known $AC^0$ lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth-$2$ circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of \(2^{N^{1-o(1)}}\) for MCSP.