The Library
Beyond natural proofs : hardness magnification and locality
Tools
Chen, Lijie, Hirahara, Shuichi, Carboni Oliveira, Igor, Pich, Jan, Rajgopal, Ninad and Santhanam, Rahul (2020) Beyond natural proofs : hardness magnification and locality. In: Innovations in Theoretical Computer Science, Seattle, USA, 12-14 Jan 2020. Published in: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 151 70 :1-70 :48. ISBN 9783959771344. doi:10.4230/LIPIcs.ITCS.2020.70
|
PDF
WRAP-beyond-natural-proofs-hardness-magnification-locality-Oliveira-2019.pdf - Accepted Version - Requires a PDF viewer. Download (667Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.70
Abstract
Hardness magnification reduces major complexity separations (such as EXP ⊈ NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M. McKay et al., 2019; Lijie Chen and Roei Tell, 2019; Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019; Igor Carboni Oliveira, 2019; Lijie Chen et al., 2019] 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 [Alexander A. Razborov and Steven Rudich, 1997]? - 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 MCSP imply the non-existence of natural proofs. As a corollary of our result, 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: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | 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, Computer science, Machine theory, Computable functions | ||||||||||||||||||
Journal or Publication Title: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | ||||||||||||||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||||||||||||||
ISBN: | 9783959771344 | ||||||||||||||||||
Official Date: | 2020 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 151 | ||||||||||||||||||
Page Range: | 70 :1-70 :48 | ||||||||||||||||||
DOI: | 10.4230/LIPIcs.ITCS.2020.70 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 22 November 2019 | ||||||||||||||||||
Date of first compliant Open Access: | 25 November 2019 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | Innovations in Theoretical Computer Science | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Seattle, USA | ||||||||||||||||||
Date(s) of Event: | 12-14 Jan 2020 | ||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year