Resolution Lower Bounds for Refutation Statements For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in (Atserias, Muller 2019) asks whether a certain natural propositional encoding of the above statement is hard for Resolution. We answer by giving an exponential size lower bound. (2) We show exponential resolution size lower bounds for reflection principles, thereby improving a result in (Atserias, Bonet 2004). (3) We provide new examples of CNFs that exponentially separate Res(2) from Resolution (an exponential separation of these two proof systems was originally proved in (Segerlind, Buss, Impagliazzo 2004)).

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?