Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Cumulative space in black-white pebbling and resolution

Alwen, Joël ; De Rezende, Susanna F. LU orcid ; Nordström, Jakob LU and Vinyals, Marc (2017) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 In Leibniz International Proceedings in Informatics, LIPIcs 67.
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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Clause Space, Cumulative Space, Parallel Resolution, Pebble Game, Pebbling, Proof Complexity, Resolution, Space
host publication
8th Innovations in Theoretical Computer Science Conference, ITCS 2017
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Papadimitriou, Christos H.
volume
67
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
8th Innovations in Theoretical Computer Science Conference, ITCS 2017
conference location
Berkeley, United States
conference dates
2017-01-09 - 2017-01-11
external identifiers
  • scopus:85034241142
ISSN
1868-8969
ISBN
9783959770293
DOI
10.4230/LIPIcs.ITCS.2017.38
language
English
LU publication?
no
id
73500bf4-c96a-4903-8ddc-f5e15e945920
date added to LUP
2020-12-18 22:19:47
date last changed
2022-04-03 07:05:17
@inproceedings{73500bf4-c96a-4903-8ddc-f5e15e945920,
  abstract     = {{<p>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.</p>}},
  author       = {{Alwen, Joël and De Rezende, Susanna F. and Nordström, Jakob and Vinyals, Marc}},
  booktitle    = {{8th Innovations in Theoretical Computer Science Conference, ITCS 2017}},
  editor       = {{Papadimitriou, Christos H.}},
  isbn         = {{9783959770293}},
  issn         = {{1868-8969}},
  keywords     = {{Clause Space; Cumulative Space; Parallel Resolution; Pebble Game; Pebbling; Proof Complexity; Resolution; Space}},
  language     = {{eng}},
  month        = {{11}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics, LIPIcs}},
  title        = {{Cumulative space in black-white pebbling and resolution}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.38}},
  doi          = {{10.4230/LIPIcs.ITCS.2017.38}},
  volume       = {{67}},
  year         = {{2017}},
}