Standard
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. / de Rezende, Susanna F.; Nordstrom, Jakob; Meir, Or; Robere, Robert.
34th Computational Complexity Conference (CCC 2019), Proceedings. Bind 137 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. s. 1-16 18 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 137).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
de Rezende, SF
, Nordstrom, J, Meir, O & Robere, R 2019,
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. i
34th Computational Complexity Conference (CCC 2019), Proceedings. bind 137, 18, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Leibniz International Proceedings in Informatics, LIPIcs, bind 137, s. 1-16, 34th Computational Complexity Conference, CCC 2019, New Brunswick, USA,
18/07/2019.
https://doi.org/10.4230/LIPIcs.CCC.2019.18APA
de Rezende, S. F.
, Nordstrom, J., Meir, O., & Robere, R. (2019).
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. I
34th Computational Complexity Conference (CCC 2019), Proceedings (Bind 137, s. 1-16). [18] Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. Leibniz International Proceedings in Informatics, LIPIcs Bind 137
https://doi.org/10.4230/LIPIcs.CCC.2019.18Vancouver
de Rezende SF
, Nordstrom J, Meir O, Robere R.
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. I 34th Computational Complexity Conference (CCC 2019), Proceedings. Bind 137. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 2019. s. 1-16. 18. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 137).
https://doi.org/10.4230/LIPIcs.CCC.2019.18Author
de Rezende, Susanna F. ; Nordstrom, Jakob ; Meir, Or ; Robere, Robert. / Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. 34th Computational Complexity Conference (CCC 2019), Proceedings. Bind 137 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. s. 1-16 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 137).
Bibtex
@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",
}
RIS
TY - GEN
T1 - Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
AU - de Rezende, Susanna F.
AU - Nordstrom, Jakob
AU - Meir, Or
AU - Robere, Robert
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - proof complexity
KW - Nullstellensatz
KW - pebble games
KW - trade-offs
KW - size
KW - degree
U2 - 10.4230/LIPIcs.CCC.2019.18
DO - 10.4230/LIPIcs.CCC.2019.18
M3 - Article in proceedings
VL - 137
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 16
BT - 34th Computational Complexity Conference (CCC 2019), Proceedings
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
T2 - 34th Computational Complexity Conference, CCC 2019
Y2 - 18 July 2019 through 20 July 2019
ER -
