Cumulative space in black-white pebbling and resolution

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

Abstract

We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko 2015] as a tool for obtaining results in cryptography. We consider instead the nondeterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10-15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström 2008, 2011], we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.

Detaljer

Författare
Externa organisationer
  • Institute of Science and Technology Austria
  • KTH Royal Institute of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikation8th Innovations in Theoretical Computer Science Conference, ITCS 2017
RedaktörerChristos H. Papadimitriou
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektroniskt)9783959770293
StatusPublished - 2017 nov 1
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, USA
Varaktighet: 2017 jan 92017 jan 11

Publikationsserier

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

Konferens

Konferens8th Innovations in Theoretical Computer Science Conference, ITCS 2017
LandUSA
OrtBerkeley
Period2017/01/092017/01/11