---
abstract: |
    Hardness magnification reduces major complexity separations (such as $\mathsf{\mathsf{EXP}} \nsubseteq \mathsf{NC}^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [@OS18_mag_first; @MMW_STOC_paper; @CT19_STOC; @OPS19_CCC; @CMMW_CCC_paper; @DBLP:conf/icalp/Oliveira19; @Magnification_FOCS19] 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 *[@DBLP:journals/jcss/RazborovR97]*?*

    – *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 [${\sf 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.
author:
- 'Lijie Chen[^1]\'
- 'Shuichi Hirahara[^2]\'
- 'Igor C. Oliveira[^3]\'
- 'Ján Pich[^4]\'
- 'Ninad Rajgopal[^5]\'
- |
    Rahul Santhanam[^6]\
     \
bibliography:
- 'refs.bib'
title: |
    Beyond Natural Proofs:\
    Hardness Magnification and Locality
---

Preliminaries {#s:preliminaries}
=============

Magnification Frontiers {#a:improved_magnification_MCSP}
=======================

Hardness Magnification and Natural Proofs {#s:non-natural}
=========================================

The Locality Barrier {#s:difficulties}
====================

Acknowledgements {#acknowledgements .unnumbered}
================

Part of this work was completed while some of the authors were visiting the Simons Institute for the Theory of Computing. We are grateful to the Simons Institute for their support. This work was supported in part by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement no. 615075. Ján Pich was supported in part by Grant 19-05497S of GA ČR. Lijie Chen is supported by NSF CCF-1741615 and a Google Faculty Research Award. Igor C. Oliveira was supported in part by a Royal Society University Research Fellowship.[^7]

Review of Hardness Magnification in Circuit Complexity {#a:review_magnification}
======================================================

[^1]: `lijieche@mit.edu`

[^2]: `s_hirahara@nii.ac.jp`

[^3]: `igor.oliveira@warwick.ac.uk`

[^4]: `jan.pich@cs.ox.ac.uk`

[^5]: `ninad.rajgopal@cs.ox.ac.uk`

[^6]: `rahul.santhanam@cs.ox.ac.uk`

[^7]: Most of this work was completed while Igor C. Oliveira was affiliated with the University of Oxford.
