---
_id: '1175'
abstract:
- lang: eng
text: 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.
alternative_title:
- LIPIcs
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Susanna
full_name: De Rezende, Susanna
last_name: De Rezende
- first_name: Jakob
full_name: Nordstrom, Jakob
last_name: Nordstrom
- first_name: Marc
full_name: Vinyals, Marc
last_name: Vinyals
citation:
ama: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white
pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38'
apa: 'Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative
space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol.
67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer
Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2017.38'
chicago: Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative
Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou,
67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38.
ieee: 'J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space
in black-white pebbling and resolution,” presented at the ITCS: Innovations in
Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.'
ista: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in
black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 67, 38:1-38-21.'
mla: Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution.
Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.
short: J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou
(Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.
conference:
end_date: 2017-01-11
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2017-01-09
date_created: 2018-12-11T11:50:33Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T06:48:51Z
day: '01'
ddc:
- '005'
- '600'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.ITCS.2017.38
editor:
- first_name: Christos
full_name: Papadimitriou, Christos
last_name: Papadimitriou
file:
- access_level: open_access
checksum: dbc94810be07c2fb1945d5c2a6130e6c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:11Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5263'
file_name: IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf
file_size: 557769
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 67'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 38:1-38-21
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6179'
pubrep_id: '927'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cumulative space in black-white pebbling and resolution
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2017'
...