--- _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' ...