Beyond Natural Proofs: Hardness Magnification and Locality Hardness magnification reduces major complexity separations (such as mathsfmathsfEXP nsubseteq mathsfNC1) 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.  this :77,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:  hardness magnification :113,avoid the natural proofs barrier of Razborov and Rudich RR97?  we :126,adapt known lower bound techniques to establish the desired lower bound for Q?

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms. We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in textQuasiNP  textNTIMEn(log n)O(1) and textNEXP do not have small circuits from various circuit classes cal C, by showing that cal C admits nontrivial satisfiability andor SAT algorithms which beat exhaustive search by a minor amount.  this :62,paper, we present a new strong lower bound consequence of nontrivial SAT algorithm for a circuit class mathcal C. Say a symmetric Boolean function f(x_1,ldots,x_n) is sparse if it outputs 1 on O(1) values of sum_i x_i. We show that for every sparse f, and for all typical cal C, faster SAT algorithms for cal C circuits actually imply lower bounds against the circuit class f circ cal C, which may be stronger than cal C itself. In particular:  algorithms for :143,168,nksize cal Ccircuits running in 2nnk time (for all k) imply textNEXP does not have f circ cal Ccircuits of polynomial size.  algorithms for 2nepsilonsize cal Ccircuits running in 2nnepsilon time (for some epsilon u003e 0) imply textQuasiNP does not have f circ cal Ccircuits of polynomial size.  SAT algorithms from the :195,literature, one immediate corollary of our results is that textQuasiNP does not have textEMAJ circ textACC0 circ textTHR circuits of polynomial size, where textEMAJ is the exact majority function, improving previous lower bounds against textACC0 Williams JACMu002714 and textACC0 circ textTHR Williams STOCu002714, MurrayWilliams STOCu002718. This is the first nontrivial lower bound against such a circuit class.