Hardness Magnification
summary
Magnification claims that a barely superlinear lower bound — roughly n^{1+ε} — for very specific problems yields superpolynomial circuit or formula lower bounds for explicit functions. Examples: if K-vertex-cover with K = log^C n resists almost-linear AC0 circuits then NP requires superpolynomial formulas; an average-case MCSP with size 2^{o(n)} and gap 1−Δ (Δ exponentially small, e.g. <2^{-0.99 n}) needing superlinear formulas implies NP not in NC1. Proofs use kernelization/parameterized reductions, random projections, PCP/witness techniques and connections between AC0, NC1 and formula complexity.
AI-written summary · about