Cumulative space in black-white pebbling and resolution Conference Paper


Author(s): Alwen, Joël; de Rezende, Susanna F; Nordstrom, Jakob; Vinyals, Marc
Title: Cumulative space in black-white pebbling and resolution
Title Series: LIPIcs
Affiliation IST Austria
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 ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic 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 ’08, ’11] 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.
Keywords: proof complexity; Pebbling; resolution; Pebble game; space; cumulative space; clause space; parallel resolution
Conference Title: ITCS: Innovations in Theoretical Computer Science
Volume: 67
Conference Dates: January 9-11, 2017
Conference Location: Berkeley, CA, USA
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2017-01-01
Start Page: Article number: 38
Sponsor: (FP7/2007–2013) / ERC grant agreement no. 279611; Swedish Research Council grants 621-2010-4797 and 621-2012-5645
URL:
DOI: 10.4230/LIPIcs.ITCS.2017.38
Notes: The authors wish to thank Yuval Filmus for making us aware of each other’s existence and thus providing the stimulus for the joint work that led up to this paper. Different subsets of the authors are grateful to Ilario Bonacina, with whom we had stimulating discussions during various stages of this project and who, in particular, provided valuable insights on dispersion, and to Adam Schill Collberg and Jan Elffers for helpful discussions on random permutation graphs.
Open access: yes (OA journal)
IST Austria Authors
  1. Joel Alwen
    13 Alwen
Related IST Austria Work