Beyond natural proofs: Hardness magnification and locality

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00523269" target="_blank" >RIV/67985840:_____/20:00523269 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.70" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.70</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ITCS.2020.70" target="_blank" >10.4230/LIPIcs.ITCS.2020.70</a>

Result language

angličtina

Original language name

Beyond natural proofs: Hardness magnification and locality

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA19-05497S" target="_blank" >GA19-05497S: Complexity of mathematical proofs and structures</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

ISBN

978-3-95977-134-4

ISSN

1868-8969

e-ISSN

—

Number of pages

48

Pages from-to

70

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Seattle

Event date

Jan 12, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—