{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:16:49Z","timestamp":1769843809400,"version":"3.49.0"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031917356","type":"print"},{"value":"9783031917363","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91736-3_7","type":"book-chapter","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:03:39Z","timestamp":1747865019000},"page":"109-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Red-Blue Pebbling with\u00a0Multiple Processors: Time, Communication and\u00a0Memory Trade-Offs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-2152-022X","authenticated-orcid":false,"given":"Toni","family":"B\u00f6hnlein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6667-802X","authenticated-orcid":false,"given":"P\u00e1l Andr\u00e1s","family":"Papp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8842-3689","authenticated-orcid":false,"given":"Albert-Jan N.","family":"Yzelman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"issue":"1\u20132","key":"7_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P., Pitassi, T., Wu, Y.: Inapproximability of treewidth, one-shot pebbling, and related layout problems. In: International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 13\u201324. Springer (2012)","DOI":"10.1007\/978-3-642-32512-0_2"},{"issue":"4","key":"7_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)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_CR4","first-page":"1","volume":"4","author":"G Bilardi","year":"2018","unstructured":"Bilardi, G., Scquizzato, M., Silvestri, F.: A lower bound technique for communication in BSP. ACM Trans. Parallel Comput. (TOPC) 4(3), 1\u201327 (2018)","journal-title":"ACM Trans. Parallel Comput. (TOPC)"},{"key":"7_CR5","unstructured":"Blelloch, G.E., Chowdhury, R.A., Gibbons, P.B., Ramachandran, V., Chen, S., Kozuch, M.: Provably good multicore cache performance for divide-and-conquer algorithms. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 501\u2013510 (2008)"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Blocki, J., Holman, B., Lee, S.: The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs. In: Theory of Cryptography Conference, pp. 52\u201379 (2022)","DOI":"10.1007\/978-3-031-22318-1_3"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Blocki, J., Ren, L., Zhou, S.: Bandwidth-hard functions: reductions and lower bounds. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1820\u20131836 (2018)","DOI":"10.1145\/3243734.3243773"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6hnlein, T., Papp, P.A., Yzelman, A.N.: Red-blue pebbling with multiple processors: time, communication and memory trade-offs (full version). arXiv preprint arXiv:2409.03898 (2024)","DOI":"10.1145\/3626183.3660269"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Carpenter, T., Rastello, F., Sadayappan, P., Sidiropoulos, A.: Brief announcement: approximating the I\/O complexity of one-shot red-blue pebbling. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 161\u2013163 (2016)","DOI":"10.1145\/2935764.2935807"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 207\u2013216 (2008)","DOI":"10.1145\/1378533.1378574"},{"key":"7_CR11","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, pp. 33\u201339 (1974)","DOI":"10.1145\/800119.803882"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: An observation on time-storage trade off. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 29\u201333 (1973)","DOI":"10.1145\/800125.804032"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Liu, Q.C.: Inapproximability of the standard pebble game and hard to pebble graphs. In: Workshop on Algorithms and Data Structures, pp. 313\u2013324. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_27"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Liu, Q.C.: Red-blue pebble game: complexity of computing the trade-off between cache size and memory transfers. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 195\u2013204 (2018)","DOI":"10.1145\/3210377.3210387"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0022-0000(85)90011-X","volume":"30","author":"PW Dymond","year":"1985","unstructured":"Dymond, P.W., Tompa, M.: Speedups of deterministic machines by synchronous parallel machines. J. Comput. Syst. Sci. 30(2), 149\u2013161 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Elango, V., Rastello, F., Pouchet, L.N., Ramanujam, J., Sadayappan, P.: On characterizing the data movement complexity of computational DAGs for parallel execution. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 296\u2013306 (2014)","DOI":"10.1145\/2612669.2612694"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Elango, V., Rastello, F., Pouchet, L.N., Ramanujam, J., Sadayappan, P.: On characterizing the data access complexity of programs. In: Proceedings of the 42nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 567\u2013580 (2015)","DOI":"10.1145\/2676726.2677010"},{"key":"7_CR18","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 11th Annual ACM Symposium on Theory of Computing, pp. 237\u2013248 (1979)","DOI":"10.1145\/800135.804418"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Gleinig, N., Hoefler, T.: The red-blue pebble game on trees and DAGs with large input. In: International Colloquium on Structural Information and Communication Complexity, pp. 135\u2013153. Springer (2022)","DOI":"10.1007\/978-3-031-09993-9_8"},{"issue":"2","key":"7_CR20","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Hong, J.W., Kung, H.T.: I\/O complexity: the red-blue pebble game. In: Proceedings of the 13th ACM Symposium on Theory of Computing, pp. 326\u2013333 (1981)","DOI":"10.1145\/800076.802486"},{"issue":"2","key":"7_CR22","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 (JACM) 24(2), 332\u2013337 (1977)","journal-title":"J. ACM (JACM)"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Jain, S., Zaharia, M.: Spectral lower bounds on the I\/O complexity of computation graphs. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 329\u2013338 (2020)","DOI":"10.1145\/3350755.3400210"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Kwasniewski, G., et al.: Pebbles, graphs, and a pinch of combinatorics: towards tight I\/O lower bounds for statically analyzable programs. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 328\u2013339 (2021)","DOI":"10.1145\/3409964.3461796"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Kwasniewski, G., Kabi\u0107, M., Besta, M., VandeVondele, J., Solc\u00e0, R., Hoefler, T.: Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1\u201322 (2019)","DOI":"10.1145\/3295500.3356181"},{"issue":"4","key":"7_CR26","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/322344.322354","volume":"29","author":"T Lengauer","year":"1982","unstructured":"Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM (JACM) 29(4), 1087\u20131130 (1982)","journal-title":"J. ACM (JACM)"},{"issue":"3\u20134","key":"7_CR27","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/PL00008264","volume":"24","author":"W McColl","year":"1999","unstructured":"McColl, W., Tiskin, A.: Memory-efficient matrix computations in the BSP model. Algorithmica 24(3\u20134), 287\u2013297 (1999)","journal-title":"Algorithmica"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Papp, P.A., Wattenhofer, R.: On the hardness of red-blue pebble games. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 419\u2013429 (2020)","DOI":"10.1145\/3350755.3400278"},{"key":"7_CR29","unstructured":"Papp, P.A., Anegg, G., Yzelman, A.N.: DAG scheduling in the BSP model (2023). arXiv preprint arXiv:2303.05989"},{"key":"7_CR30","unstructured":"Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119\u2013127 (1970)"},{"key":"7_CR31","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2011.12.005","volume":"14","author":"D Ranjan","year":"2012","unstructured":"Ranjan, D., Savage, J., Zubair, M.: Upper and lower I\/O bounds for pebbling R-pyramids. J. Discrete Algorithms 14, 2\u201312 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"7_CR32","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1145\/322217.322233","volume":"27","author":"R Reischuk","year":"1980","unstructured":"Reischuk, R.: Improved bounds on the problem of time-space trade-off in the pebble game. J. ACM (JACM) 27(4), 839\u2013849 (1980)","journal-title":"J. ACM (JACM)"},{"key":"7_CR33","doi-asserted-by":"crossref","unstructured":"Savage, J.E.: Extending the Hong-Kung model to memory hierarchies. In: International Computing and Combinatorics Conference, pp. 270\u2013281. Springer (1995)","DOI":"10.1007\/BFb0030842"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Savage, J.E., Zubair, M.: A unified model for multicore architectures. In: Proceedings of the 1st International Forum on Next-Generation Multicore\/manycore Technologies, pp. 1\u201312 (2008)","DOI":"10.1145\/1463768.1463780"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Scott, J., Holtz, O., Schwartz, O.: Matrix multiplication I\/O-complexity by path routing. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 35\u201345 (2015)","DOI":"10.1145\/2755573.2755594"},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"Sethi, R.: Complete register allocation problems. In: Proceedings of the 5th ACM Symposium on Theory of Computing, pp. 182\u2013195 (1973)","DOI":"10.1145\/800125.804049"},{"issue":"1","key":"7_CR37","first-page":"1","volume":"3","author":"E Solomonik","year":"2017","unstructured":"Solomonik, E., Carson, E., Knight, N., Demmel, J.: Trade-offs between synchronization, communication, and computation in parallel linear algebra computations. ACM Trans. Parallel Comput. (TOPC) 3(1), 1\u201347 (2017)","journal-title":"ACM Trans. Parallel Comput. (TOPC)"},{"issue":"1\u20132","key":"7_CR38","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(97)00197-7","volume":"196","author":"A Tiskin","year":"1998","unstructured":"Tiskin, A.: The bulk-synchronous parallel random access machine. Theoret. Comput. Sci. 196(1\u20132), 109\u2013130 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"8","key":"7_CR39","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"issue":"1","key":"7_CR40","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jcss.2010.06.012","volume":"77","author":"LG Valiant","year":"2011","unstructured":"Valiant, L.G.: A bridging model for multi-core computing. J. Comput. Syst. Sci. 77(1), 154\u2013166 (2011)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91736-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:03:53Z","timestamp":1747865033000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91736-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031917356","9783031917363"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91736-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delphi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.torontomu.ca\/sirocco-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}