Nullstellensatz size-degree trade-offs from reversible pebbling
(2019) 34th Computational Complexity Conference, CCC 2019 In Leibniz International Proceedings in Informatics, LIPIcs 137.- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/66e053a2-17f1-495d-b02d-262c0a196726
- author
- De Rezende, Susanna F. LU ; Nordström, Jakob LU ; Meir, Or and Robere, Robert
- publishing date
- 2019-07-01
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Degree, Nullstellensatz, Pebble games, Proof complexity, Size, Trade-offs
- host publication
- 34th Computational Complexity Conference, CCC 2019
- series title
- Leibniz International Proceedings in Informatics, LIPIcs
- editor
- Shpilka, Amir
- volume
- 137
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 34th Computational Complexity Conference, CCC 2019
- conference location
- New Brunswick, United States
- conference dates
- 2019-07-18 - 2019-07-20
- external identifiers
-
- scopus:85070721193
- ISSN
- 1868-8969
- ISBN
- 9783959771160
- DOI
- 10.4230/LIPIcs.CCC.2019.18
- language
- English
- LU publication?
- no
- id
- 66e053a2-17f1-495d-b02d-262c0a196726
- date added to LUP
- 2020-12-18 22:17:39
- date last changed
- 2022-04-26 22:42:12
@inproceedings{66e053a2-17f1-495d-b02d-262c0a196726, abstract = {{<p>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.</p>}}, author = {{De Rezende, Susanna F. and Nordström, Jakob and Meir, Or and Robere, Robert}}, booktitle = {{34th Computational Complexity Conference, CCC 2019}}, editor = {{Shpilka, Amir}}, isbn = {{9783959771160}}, issn = {{1868-8969}}, keywords = {{Degree; Nullstellensatz; Pebble games; Proof complexity; Size; Trade-offs}}, language = {{eng}}, month = {{07}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, series = {{Leibniz International Proceedings in Informatics, LIPIcs}}, title = {{Nullstellensatz size-degree trade-offs from reversible pebbling}}, url = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2019.18}}, doi = {{10.4230/LIPIcs.CCC.2019.18}}, volume = {{137}}, year = {{2019}}, }