{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:23:27Z","timestamp":1777965807216,"version":"3.51.4"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319621265","type":"print"},{"value":"9783319621272","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62127-2_27","type":"book-chapter","created":{"date-parts":[[2017,7,4]],"date-time":"2017-07-04T02:47:31Z","timestamp":1499136451000},"page":"313-324","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quanquan C.","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"key":"27_CR1","unstructured":"Alwen, J., de Rezende, S.F., Nordstr\u00f6m, J., Vinyals, M.: Cumulative space in black-white pebbling and resolution. In: Innovations in Theoretical Computer Science, ITCS 2017, Berkeley, CA, USA, pp. 9\u201311, January 2017"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, pp. 595\u2013603 (2015). http:\/\/doi.acm.org\/10.1145\/2746539.2746622","DOI":"10.1145\/2746539.2746622"},{"issue":"4","key":"27_CR3","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"18","author":"CH Bennett","year":"1989","unstructured":"Bennett, C.H.: Time\/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766\u2013776 (1989). http:\/\/dx.doi.org\/10.1137\/0218053","journal-title":"SIAM J. Comput."},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Chan, S.M., Lauria, M., Nordstr\u00f6m, J., Vinyals, M.: Hardness of approximation in PSPACE and separation results for pebble games. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, October 17\u201320, 2015, pp. 466\u2013485 (2015). http:\/\/dx.doi.org\/10.1109\/FOCS.2015.36","DOI":"10.1109\/FOCS.2015.36"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S., Sethi, R.: Storage requirements for deterministic \/ polynomial time recognizable languages. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 33\u201339. ACM, New York (1974). http:\/\/doi.acm.org\/10.1145\/800119.803882","DOI":"10.1145\/800119.803882"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Liu, Q.C.: Inapproximability of the standard pebble game and hard to pebble graphs. CoRR (2017)","DOI":"10.1007\/978-3-319-62127-2_27"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/3-540-09118-1_12","volume-title":"Theoretical Computer Science 4th GI Conference","author":"P van Emde Boas","year":"1979","unstructured":"van Emde Boas, P., van Leeuwen, J.: Move rules and trade-offs in the pebble game. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol. 67, pp. 101\u2013112. Springer, Heidelberg (1979). doi:10.1007\/3-540-09118-1_12"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Gilbert, J.R., Lengauer, T., Tarjan, R.E.: The pebbling problem is complete in polynomial space. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 237\u2013248. ACM, New York (1979). http:\/\/doi.acm.org\/10.1145\/800135.804418","DOI":"10.1145\/800135.804418"},{"key":"27_CR9","unstructured":"Gilbert, J.R., Tarjan, R.E.: Variations of a pebble game on graphs. Technical report, Stanford, CA, USA (1978)"},{"issue":"6","key":"27_CR10","doi-asserted-by":"publisher","first-page":"2622","DOI":"10.1137\/080713513","volume":"39","author":"P Hertel","year":"2010","unstructured":"Hertel, P., Pitassi, T.: The PSPACE-completeness of black-white pebbling. SIAM J. Comput. 39(6), 2622\u20132682 (2010). http:\/\/dx.doi.org\/10.1137\/0218053","journal-title":"SIAM J. Comput."},{"issue":"2","key":"27_CR11","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J Hopcroft","year":"1977","unstructured":"Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. ACM 24(2), 332\u2013337 (1977). http:\/\/doi.acm.org\/10.1145\/322003.322015","journal-title":"J. ACM"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Jia-Wei, H., Kung, H.T.: I\/O complexity: the red-blue pebble game. In: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, STOC 1981, pp. 326\u2013333. ACM, New York (1981). http:\/\/doi.acm.org\/10.1145\/800076.802486","DOI":"10.1145\/800076.802486"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Lengauer, T., Tarjan, R.E.: Upper and lower bounds on time-space tradeoffs. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 262\u2013277. ACM, New York (1979). http:\/\/doi.acm.org\/10.1145\/800135.804420","DOI":"10.1145\/800135.804420"},{"key":"27_CR14","unstructured":"Nordstrom, J.: New wine into old wineskins: A survey of some pebbling classics with supplemental results (2015)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC 1976, pp. 149\u2013160. ACM, New York (1976). http:\/\/doi.acm.org\/10.1145\/800113.803643","DOI":"10.1145\/800113.803643"},{"issue":"3","key":"27_CR16","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R Sethi","year":"1975","unstructured":"Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226\u2013248 (1975). http:\/\/dx.doi.org\/10.1137\/0204020","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62127-2_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:17:24Z","timestamp":1709828244000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62127-2_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319621265","9783319621272"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62127-2_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"5 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. John's","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}