Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

摘要

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 θ, for a given parameter θ. 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 1. N~(3-o(1))-size de Morgan formulas, improving the recent N(2-o(1)) lower bound by Hirahara and San-thanam (CCC, 2017), 2. 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 3. 2~(Ω(N~(1/(d+1.01))))-size depth-d AC~0 circuits, improving the (implicit, in their work) exponential size 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 optimal lower bound of 2~(Ω(N)) for MCSP.