2019/11/19 by Lijie Chen, Shuichi Hirahara, Chen, Lijie +9 · 2 citations
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Low-power high-performance VLSI design
paper · pdf · doi:10.48550/arxiv.1911.08297
openalex publication_date 2019/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hardness magnification reduces major complexity separations (such as EXP \nsubseteq NC1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] 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 [RR97]? Can we adapt known lower bound techniques to establish the desired lower bound for Q?