Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Susanna F. de Rezende, Or Meir, Jakob Nordström +3

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget wit…