Abstract
We show that for several natural problems of interest (including Vertex Cover, Satisfiability, and variants of the Minimum Circuit Size Problem), complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification''. We further explore magnification as an avenue to proving strong lower bounds, and argue that magnification circumvents the "natural proofs'' barrier of Razborov and Rudich. Examining some standard proof techniques, we find that they fall just short of proving lower bounds via magnification. As one of our main open problems, we ask whether there are other meta-mathematical barriers to proving lower bounds that rule out approaches combining magnification with known techniques.
Joint work with Rahul Santhanam (Oxford).