Nullstellensatz size-degree trade-offs from reversible pebbling

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Externa organisationer
  • KTH Royal Institute of Technology
  • University of Copenhagen
  • University of Haifa
  • Center for Discrete Mathematics and Theoretical Computer Science
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikation34th Computational Complexity Conference, CCC 2019
RedaktörerAmir Shpilka
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektroniskt)9783959771160
StatusPublished - 2019 jul 1
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang34th Computational Complexity Conference, CCC 2019 - New Brunswick, USA
Varaktighet: 2019 jul 182019 jul 20

Publikationsserier

NamnLeibniz International Proceedings in Informatics, LIPIcs
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volym137
ISSN (tryckt)1868-8969

Konferens

Konferens34th Computational Complexity Conference, CCC 2019
LandUSA
OrtNew Brunswick
Period2019/07/182019/07/20