Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Publication type: Journal Article
Publication date: 2021-02-12
scimago Q1
wos Q2
SJR: 1.103
CiteScore: 1.8
Impact factor: 1.0
ISSN: 10163328, 14208954
General Mathematics
Computational Mathematics
Computational Theory and Mathematics
Theoretical Computer Science
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.
Found
Nothing found, try to update filter.
Found
Nothing found, try to update filter.
Top-30
Journals
|
1
|
|
|
Computational Complexity
1 publication, 100%
|
|
|
1
|
Publishers
|
1
|
|
|
Springer Nature
1 publication, 100%
|
|
|
1
|
- We do not take into account publications without a DOI.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
1
Total citations:
1
Citations from 2024:
0
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
De Rezende S. F. et al. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling // Computational Complexity. 2021. Vol. 30. No. 1. 4
GOST all authors (up to 50)
Copy
De Rezende S. F., Meir O., Nordström J., Robere R. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling // Computational Complexity. 2021. Vol. 30. No. 1. 4
Cite this
RIS
Copy
TY - JOUR
DO - 10.1007/s00037-020-00201-y
UR - https://doi.org/10.1007/s00037-020-00201-y
TI - Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
T2 - Computational Complexity
AU - De Rezende, Susanna F.
AU - Meir, Or
AU - Nordström, Jakob
AU - Robere, Robert
PY - 2021
DA - 2021/02/12
PB - Springer Nature
IS - 1
VL - 30
SN - 1016-3328
SN - 1420-8954
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2021_De Rezende,
author = {Susanna F. De Rezende and Or Meir and Jakob Nordström and Robert Robere},
title = {Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling},
journal = {Computational Complexity},
year = {2021},
volume = {30},
publisher = {Springer Nature},
month = {feb},
url = {https://doi.org/10.1007/s00037-020-00201-y},
number = {1},
pages = {4},
doi = {10.1007/s00037-020-00201-y}
}