2019 · 29 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsCircuit TheoryTheory Of ComputationAlgorithmic ComplexityApproximation AlgorithmsCircuit ComplexityComplexity TheoryComputational ComplexityCircuit Lower BoundsCircuit Size ComplexityCircuit Upper BoundsComplexity ClassesCompressionHardnessHardness MagnificationLower Bounds
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.
19
Alexander Razborov, Steven Rudich · Journal of Computer and System Sciences · 1997 · 482 citations
Scott Aaronson, Avi Wigderson · ACM Transactions on Computation Theory · 2009 · 156 citations