Simple general magnification of circuit lower bounds
Albert Atserias, Moritz Müller · 2025
Read Simple general magnification of circuit lower bounds by Albert Atserias, Moritz Müller (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-24061.txt.
Introduction
Albert Atserias and Moritz Müller offer a simpler lever for one of theoretical computer science's deepest games, in a 2025 paper. Hardness magnification is a strategy for proving that problems need big circuits: show that a tiny improvement over known limits would explode, by known theorems, into a major result. The machinery has been intricate. Their method rests on distinguishers, sparse matrices borrowing tricks from error-correcting codes.
With that one tool, earlier magnification theorems are recovered, strengthened, and unified. For instance, slightly superlinear lower bounds on formula size for approximating certain sparse problems would imply fixed-polynomial lower bounds for all of NP. The thresholds they reach are provably sharp. The approach also yields a uniform result for the minimum circuit size problem, appearing to sidestep a known barrier that blocked similar attempts.
Catalog record
| CREATOR | Albert Atserias, Moritz Müller |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-24061
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Simple general magnification of circuit lower bounds Albert Atserias, Moritz Müller Abstract We introduce a technically and conceptually simple approach to magnification of circuit and formula lower bounds. Central to the method are so-called distinguishers , sparse matrices that retain some of the key properties of error-correcting codes. As applications, we generalize and strengthen known general (not problem specific) magnification results and in particular achieve magnification thresholds below known lower bounds. For example, we show that fixed-polynomial formula-size lower bounds for 𝖭𝖯 \mathsf{NP} are implied by slightly superlinear formula-size lower bounds for approximating any sufficiently sparse problem in 𝖭𝖯 \mathsf{NP} . We also show that the thresholds achieved are sharp. Additionally, our approach yields a uniform magnification result for the Minimum Circuit Size Problem (MCSP). This seems to sidestep the localization barrier. 1 Introduction We use standard terminology and notation: by a circuit (resp. formula ) we mean one with inner gates labeled \neg,\wedge,\vee of fan-in at most 2 (and, resp., of fan-out at most 1); its size is the number of gates. A promise problem is given by disjoint sets YES and NO of binary strings. It is contained in \mathsf{SIZE}[s] (resp. \mathsf{FML}[s] ), where s:\mathbb{N}\to\mathbb{N} , if for all sufficiently large n\in\mathbb{N} there is a circuit (resp. formula) C_{n} of size \leqslant s(n) that accepts all n -bit strings in YES and rejects all n -bit strings in NO. The class \mathsf{P}\textit{-uniform-}\mathsf{SIZE}[s] additionally requires the map n\mapsto C_{n} to be computable in time polynomial in n . Note \mathsf{P/poly}=\mathsf{SIZE}[n^{O(1)}] and \mathsf{NC}_{1}=\mathsf{FML}[n^{O(1)}] . 1.1 Why are circuit lower bounds difficult? The non-uniform version of \mathsf{P}\neq\mathsf{NP} asks for a problem in \mathsf{NP} that is not decided by circuits of polynomial size, i.e., to show \mathsf{NP}\not\subseteq\mathsf{P/poly} . This seems to be out of reach of current techniques. Today not even fixed-polynomial size lower bounds are known, not even for \mathsf{NE} and formulas, i.e., whether \mathsf{NE}\not\subseteq\mathsf{FML}[n^{c}] for all c\in\mathbb{N} , equivalently \mathsf{NEXP}\not\subseteq\mathsf{NC}_{1} . Why are circuit lower bounds so difficult? The natural proof barrier [ 33 ] points out some limitation of current techniques – the notion of a natural proof is, however, informal. Razborov’s program [ 31 ] asks for a formally precise barrier in form of a natural theory that proves known weak lower bounds (cf. [ 31 , 25 ] ) and does not prove strong conjectured ones. The unprovability is, ironically, again dubbed to be out of reach of current techniques – of proof complexity (cf. [ 32 ] , [ 20 , Chapter 27-30] ). A more direct approach to somehow explain the apparent hardness of circuit lower bounds is to try to establish that the Minimum Circuit Size Problem is computationally hard in some sense. Namely, for \sigma:\mathbb{N}\to\mathbb{N} , \mathsf{MCSP}[\sigma] Input: x\in\{0,1\}^{n} with n=2^{\ell} for some n,\ell\in\mathbb{N} . Problem: is x computable by a circuit of size \leqslant\sigma(\ell) ? Here, that x is computed by a circuit C means that C has \ell inputs and outputs the i -th bit of x when given the lexicographically i -th \ell -bit string as input. Research into the complexity of \mathsf{MCSP}[\sigma] dates back to the 1950s [ 36 ] and intensified in recent years, starting with [ 19 ] . By the idea that its computational hardness reflects the difficulty of proving circuit lower bounds, \mathsf{MCSP}[\sigma] is expected to become harder for larger \sigma but this is not known. Concerning its envisioned hardness we refer to [ 1 ] for a survey and mention here only an obstacle: \mathsf{MCSP}[2^{o(\ell)}] is 2^{n^{o(1)}} -sparse and Buhrmann and Hitchcock [ 4 ] showed that such problems are not \mathsf{NP} -hard unless \mathsf{PH} collapses. Recall, for q:\mathbb{N}\to\mathbb{N} , a problem Q is q -sparse if |Q\cap\{0,1\}^{n}|\leqslant q(n) for all n\in\mathbb{N} . 1.2 Magnification Thus, not only seem strong circuit lower bounds to be out of reach of current techniques, there is also a lack of understanding of what this very statement means. This is strikingly emphasized by what Oliveira and Santhanam [ 27 ] called magnification results: a strong lower bound that appear(ed) out of reach of current techniques is implied by a lower bound that is “almost known” – meaning that there are known lower bounds that are only marginally weaker or concern slight variations of the problem or the computational model. Such results are interesting, first, because they unveil inconsistencies in our intuitions for what is or not within reach of current techniques. Second, they provide an approach to strong lower bounds that sidesteps the natural proof barrier – see [ 9 ] for an insightful discussion. Both perspectives focus attention on the magnification threshold – the “almost known” lower bound. The initial magnification result from [ 27 ] concerns a promise problem relaxing \mathsf{MCSP}[\sigma] , namely its approximation version: for \epsilon:\mathbb{N}\to\mathbb{R}_{>0} \epsilon - \mathsf{MCSP}[\sigma] Input: x\in\{0,1\}^{n} with n=2^{\ell} for some n,\ell\in\mathbb{N} . YES: x is computable by a circuit of size \leqslant\sigma(\ell) . NO: d_{H}(x,y)\geqslant\epsilon(n)\cdot n for all y\in\{0,1\}^{n} computable by a circuit of size \leqslant\sigma(\ell) . Here, d_{H}(x,y) is the Hamming distance of x,y . In other words, NO instances are truth tables of functions that are not (1-\epsilon(n)) -approximable by circuits of size \leqslant\sigma(\ell) . Observe, the smaller \epsilon , the more NO instances, the harder the problem, and \epsilon\text{-}\mathsf{MCSP}[\sigma] is the same as \mathsf{MCSP}[\sigma] if \epsilon(n)\leqslant 1/n for all n>0 . Under cryptographic assumptions, it is known that 1/3 - \mathsf{MCSP}[2^{\sqrt{\ell}}]\notin\mathsf{P/poly} (cf. [ 27 ] ). Theorem 1 ( [ 27 ] ) . \mathsf{NP}\not\subseteq\mathsf{NC}_{1} if there exists a real \delta>0 such that n^{-o(1)}\text{-}\mathsf{MCSP}[2^{\sqrt{\ell}}]\not\in\mathsf{FML}[n^{1+\delta}]. This magnification threshold can be considered to be “almost known”: Theorem 2 ( [ 15 ] ) . \mathsf{MCSP}[2^{\sqrt{\ell}}]\notin\mathsf{FML}[n^{2-\delta}] for all reals \delta>0 . Following [ 27 ] a wide variety of magnification results have been discovered, with magnification thresholds concerning almost formulas [ 9 ] , probabilistic formulas [ 7 ] , zero-error heuristics [ 27 , 6 ] , sublinear randomized algorithms [ 27 ] , streaming algorithms [ 23 ] , refuters [ 27 , 8 ] or obstruction sets [ 7 ] . A few magnification results have also been found in proof complexity [ 25 , 3 ] . We do not attempt a survey and refer to [ 9 ] for a systematic overview. A central role is played by \mathsf{MCSP}[\sigma] and its variants. Besides the mentioned approximation relaxation, prominently its gap relaxation (e.g. [ 27 , 28 , 9 ] ), its search version [ 23 ] and their siblings for time-bounded Kolmogoroff complexity instead circuit complexity. Many proofs of magnification results build on deep results in complexity theory, and many are somewhat ad hoc, exploiting special properties of the \mathsf{MCSP}[\sigma] variants. 1.3 General magnification As for a more principled approach, a significant step forward was taken by Chen et al. [ 6 ] . Only the sparsity matters: “analogous weak circuit lower bounds […] for any equally-sparse \mathsf{NP} language also imply major separations in circuit complexity.” We refer to such results as general magnification. An example predating [ 6 ] is Theorem 3 ( [ 10 ] ) . \mathsf{NEXP}\not\subseteq\mathsf{P/poly} if there exists an 2^{n^{o(1)}} -sparse problem Q\in\mathsf{NP} such that Q\not\in\mathsf{SIZE}[n^{1+o(1)}]. In [ 6 ] the conclusion is strengthened to \mathsf{NP}\not\subseteq\mathsf{SIZE}[n^{c}] for all c\in\mathbb{N}