Cumulative space in black-white pebbling and resolution
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Cumulative space in black-white pebbling and resolution. / Alwen, Joël; De Rezende, Susanna F.; Nordström, Jakob; Vinyals, Marc.
8th Innovations in Theoretical Computer Science Conference, ITCS 2017. ed. / Christos H. Papadimitriou. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 67).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Cumulative space in black-white pebbling and resolution
AU - Alwen, Joël
AU - De Rezende, Susanna F.
AU - Nordström, Jakob
AU - Vinyals, Marc
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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.
AB - 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.
KW - Clause Space
KW - Cumulative Space
KW - Parallel Resolution
KW - Pebble Game
KW - Pebbling
KW - Proof Complexity
KW - Resolution
KW - Space
UR - http://www.scopus.com/inward/record.url?scp=85034241142&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2017.38
DO - 10.4230/LIPIcs.ITCS.2017.38
M3 - Article in proceedings
AN - SCOPUS:85034241142
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
A2 - Papadimitriou, Christos H.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Y2 - 9 January 2017 through 11 January 2017
ER -
ID: 251867754