Hardness Magnification and the Locality Barrier

10^th February 2021, 14:00 Online MT CSACTOO365Team
Ninad Rajgopal
University of Oxford

Abstract

Hardness magnification reduces major complexity separations (such as EXP is not in NC1 or NP is not in P/Poly) to proving lower bounds for some natural problem Q (like the Minimum Circuit Size Problem - MCSP) against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19, CJW20] 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 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: Can we adapt known lower bound techniques to establish the desired lower bound for Q?

Hardness magnification might sidestep the Razborov-Rudich natural proofs barrier [RR97], 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.

This talk will be based on joint work with Lijie Chen, Shuichi Hirahara, Igor C.Oliveira, Jan Pich and Rahul Santhanam,

Additional Materials

• https://eccc.weizmann.ac.il/report/2019/168/