@inproceedings{3d2d6c7342b746408620ea718c4dad1e,
title = "Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling",
abstract = "We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formula over G in size t+1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.",
keywords = "proof complexity, Nullstellensatz, pebble games, trade-offs, size, degree",
author = "{de Rezende}, {Susanna F.} and Jakob Nordstrom and Or Meir and Robert Robere",
year = "2019",
doi = "10.4230/LIPIcs.CCC.2019.18",
language = "English",
volume = "137",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
pages = "1--16",
booktitle = "34th Computational Complexity Conference (CCC 2019), Proceedings",
note = "34th Computational Complexity Conference, CCC 2019 ; Conference date: 18-07-2019 Through 20-07-2019",
}