Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
Dylan M. McKay, Cody D. Murray, Ryan Williams · 2019
The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem using bounded-size circuits. Recently, Oliveira and Santhanam [FOCS 2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a “hardness magnification” phenomenon for MCSP in restricted settings. Letting MCSP[s(n)] be the problem of deciding if a truth table of length 2n has circuit complexity at most s(n), they proved that small (fixed-polynomial) average case circuit/formula lower bounds for MCSP[2√n], or lower bounds for approximating MCSP[2o(n)], would imply major separations such as NP ⊄BPP and NP ⊄P/poly.