The Library
Beyond natural proofs : hardness magnification and locality
Tools
Chen, Lijie, Hirahara, Shuichi, Oliveira, Igor Carboni, Pich, Ján, Rajgopal, Ninad and Santhanam, Rahul (2022) Beyond natural proofs : hardness magnification and locality. Journal of the ACM, 69 (4). 25. doi:10.1145/3538391 ISSN 0004-5411.
|
PDF
WRAP-Beyond-natural-proofs-hardness-magnification-locality-22.pdf - Accepted Version - Requires a PDF viewer. Download (829Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3538391
Abstract
Hardness magnification reduces major complexity separations (such as EXP ⊈ NC1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [11, 13, 14, 40, 42, 43, 46] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds, but these are not yet sufficient for magnification.
In this work, we provide more examples of this phenomenon and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program:
– Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich [51]?
– Can we adapt known lower-bound techniques to establish the desired lower bound for Q?
We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit-size problem imply the non-existence of natural proofs. As the non-existence of natural proofs implies the non-existence of efficient learning algorithms, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms.
Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower-bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier: existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower-bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.
Item Type: | Journal Article | |||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||||||||||||||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Combinatorial analysis -- Data processing , Discrete mathematics , Computational complexity , Computer algorithms | |||||||||||||||||||||||||||||||||||||||
Journal or Publication Title: | Journal of the ACM | |||||||||||||||||||||||||||||||||||||||
Publisher: | Association for Computing Machinery, Inc. | |||||||||||||||||||||||||||||||||||||||
ISSN: | 0004-5411 | |||||||||||||||||||||||||||||||||||||||
Official Date: | 23 August 2022 | |||||||||||||||||||||||||||||||||||||||
Dates: |
|
|||||||||||||||||||||||||||||||||||||||
Volume: | 69 | |||||||||||||||||||||||||||||||||||||||
Number: | 4 | |||||||||||||||||||||||||||||||||||||||
Number of Pages: | 49 | |||||||||||||||||||||||||||||||||||||||
Article Number: | 25 | |||||||||||||||||||||||||||||||||||||||
DOI: | 10.1145/3538391 | |||||||||||||||||||||||||||||||||||||||
Status: | Peer Reviewed | |||||||||||||||||||||||||||||||||||||||
Publication Status: | Published | |||||||||||||||||||||||||||||||||||||||
Re-use Statement: | © ACM, 2022 This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Journal of the ACM, 69(4) 2022 http://doi.acm.org/10.1145/3538391 | |||||||||||||||||||||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||||||||||||||||||||
Date of first compliant deposit: | 2 November 2022 | |||||||||||||||||||||||||||||||||||||||
Date of first compliant Open Access: | 2 November 2022 | |||||||||||||||||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year