@inproceedings{66e053a217f1495db02d262c0a196726,
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 = "Degree, Nullstellensatz, Pebble games, Proof complexity, Size, Trade-offs",
author = "{De Rezende}, {Susanna F.} and Jakob Nordstr{\"o}m and Or Meir and Robert Robere",
year = "2019",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.CCC.2019.18",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Amir Shpilka",
booktitle = "34th Computational Complexity Conference, CCC 2019",
note = "34th Computational Complexity Conference, CCC 2019 ; Conference date: 18-07-2019 Through 20-07-2019",
}