Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.24061 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913906348261376 |
|---|---|
| author | Atserias, Albert Müller, Moritz |
| author_facet | Atserias, Albert Müller, Moritz |
| contents | 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 NP are implied by slightly superlinear formula-size lower bounds for approximating any sufficiently sparse problem in 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24061 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simple general magnification of circuit lower bounds Atserias, Albert Müller, Moritz Computational Complexity 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 NP are implied by slightly superlinear formula-size lower bounds for approximating any sufficiently sparse problem in 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. |
| title | Simple general magnification of circuit lower bounds |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2503.24061 |