Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • University of Haifa
  • McGill University
  • Institute of Mathematics of the Academy of Sciences of the Czech Republic
  • University of Copenhagen
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Artikelnummer4
TidskriftComputational Complexity
Volym30
Utgåva nummer1
StatusPublished - 2021
PublikationskategoriForskning
Peer review utfördJa