Nullstellensatz size-degree trade-offs from reversible pebbling

0540454 - MÚ 2022 RIV CH eng J - Journal Article
de Rezende, Susanna F. - Meir, O. - Norström, J. - Robere, R.
Nullstellensatz size-degree trade-offs from reversible pebbling.
Computational Complexity. Roč. 30, č. 1 (2021), č. článku 4. ISSN 1016-3328. E-ISSN 1420-8954
Institutional support: RVO:67985840
Keywords : nullstellensatz * pebbling * proof complexity * trade-offs
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.962, year: 2021
Method of publishing: Limited access
https://doi.org/10.1007/s00037-020-00201-y

We establish an exactly tight relation between reversiblepebblings 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 formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.
Permanent Link: http://hdl.handle.net/11104/0318083