3 papers
cs.CC2020
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Susanna F. de Rezende, Or Meir, Jakob Nordström +1
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph can be reversibly pebbl…
cs.CC2020
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…
cs.CC2015
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi +1
In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query co…