Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Nullstellensatz size-degree trade-offs from reversible pebbling

De Rezende, Susanna F. LU orcid ; Nordström, Jakob LU ; Meir, Or and Robere, Robert (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:
author
; ; and
publishing date
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}},
}