{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T05:01:49Z","timestamp":1780030909118,"version":"3.53.1"},"reference-count":38,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1016\/j.ipl.2026.106637","type":"journal-article","created":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:48:16Z","timestamp":1773272896000},"page":"106637","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["I\/O complexity and pebble games with partial computations"],"prefix":"10.1016","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1602-8329","authenticated-orcid":false,"given":"Aleksandros","family":"Sobczyk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ipl.2026.106637_bib0001","series-title":"Proceedings of 13th ACM Symposium on Theory of Computing","first-page":"326","article-title":"I\/O complexity: the red-blue pebble game","author":"Hong","year":"1981"},{"issue":"9","key":"10.1016\/j.ipl.2026.106637_bib0002","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The input\/output complexity of sorting and related problems","volume":"31","author":"Aggarwal","year":"1988","journal-title":"Commun. ACM"},{"issue":"1","key":"10.1016\/j.ipl.2026.106637_bib0003","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/wcms.1159","article-title":"cp2k: atomistic simulations of condensed matter systems","volume":"4","author":"Hutter","year":"2014","journal-title":"Wiley Interdiscipl. Rev. Comput. Mol. Sci."},{"key":"10.1016\/j.ipl.2026.106637_bib0004","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1561\/2200000035","article-title":"Randomized algorithms for matrices and data","volume":"3","author":"Mahoney","year":"2011","journal-title":"Foundat. Trend.\u00ae Mach. Learn."},{"key":"10.1016\/j.ipl.2026.106637_bib0005","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000060","article-title":"Sketching as a tool for numerical linear algebra","volume":"10","author":"Woodruff","year":"2014","journal-title":"Foundat. Trend.\u00ae Theoret. Comput. Sci."},{"key":"10.1016\/j.ipl.2026.106637_bib0006","series-title":"Convex Optimization","author":"Boyd","year":"2004"},{"key":"10.1016\/j.ipl.2026.106637_bib0007","series-title":"Numerical Linear Algebra and Optimization","author":"Gill","year":"2021"},{"key":"10.1016\/j.ipl.2026.106637_bib0008","series-title":"Iterative Methods for Sparse Linear Systems","author":"Saad","year":"2003"},{"key":"10.1016\/j.ipl.2026.106637_bib0009","series-title":"Numerical Methods for Large Eigenvalue Problems: Revised Edition","author":"Saad","year":"2011"},{"key":"10.1016\/j.ipl.2026.106637_bib0010","series-title":"Proceedings of 9th Innovations in Theoretical Computer Science Conference","first-page":"34","article-title":"Fine-grained I\/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy","author":"Demaine","year":"2018"},{"key":"10.1016\/j.ipl.2026.106637_bib0011","series-title":"Graph Algorithms in the Language of Linear Algebra","author":"Kepner","year":"2011"},{"key":"10.1016\/j.ipl.2026.106637_bib0012","first-page":"6000","article-title":"Attention is all you need","volume":"30","author":"Vaswani","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.ipl.2026.106637_bib0013","first-page":"17283","article-title":"Big bird: transformers for longer sequences","volume":"33","author":"Zaheer","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"3","key":"10.1016\/j.ipl.2026.106637_bib0014","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/321958.321970","article-title":"Optimal code generation for expression trees","volume":"23","author":"Aho","year":"1976","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/j.ipl.2026.106637_bib0015","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0201002","article-title":"Optimization of straight line programs","volume":"1","author":"Aho","year":"1972","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.ipl.2026.106637_bib0016","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/321958.321971","article-title":"Code generation for a one-register machine","volume":"23","author":"Bruno","year":"1976","journal-title":"J. ACM"},{"key":"10.1016\/j.ipl.2026.106637_bib0017","series-title":"Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures","first-page":"328","article-title":"The impact of partial computations on the red\u2013blue pebble game","author":"Papp","year":"2025"},{"key":"10.1016\/j.ipl.2026.106637_bib0018","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","article-title":"Complete register allocation problems","author":"Sethi","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ipl.2026.106637_bib0019","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0209038","article-title":"The pebbling problem is complete in polynomial space","author":"Gilbert","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ipl.2026.106637_bib0020","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF00289150","article-title":"Time-space trade-offs in a pebble game","volume":"10","author":"Wolfgang","year":"1978","journal-title":"Acta Inf."},{"key":"10.1016\/j.ipl.2026.106637_bib0021","series-title":"Workshop on Algorithms and Data Structures","first-page":"313","article-title":"Inapproximability of the standard pebble game and hard to pebble graphs","author":"Demaine","year":"2017"},{"key":"10.1016\/j.ipl.2026.106637_bib0022","series-title":"Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures","first-page":"195","article-title":"Red-blue pebble game: complexity of computing the trade-off between cache size and memory transfers","author":"Demaine","year":"2018"},{"key":"10.1016\/j.ipl.2026.106637_bib0023","series-title":"Technical Report","article-title":"Red-Blue and Standard Pebble Games: Complexity and Applications in the Sequential and Parallel Models","author":"Liu","year":"2017"},{"key":"10.1016\/j.ipl.2026.106637_bib0024","series-title":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures","first-page":"419","article-title":"On the hardness of red\u2013blue pebble games","author":"Papp","year":"2020"},{"key":"10.1016\/j.ipl.2026.106637_bib0025","series-title":"International Computing and Combinatorics Conference","first-page":"270","article-title":"Extending the Hong-Kung model to memory hierarchies","author":"Savage","year":"1995"},{"key":"10.1016\/j.ipl.2026.106637_bib0026","series-title":"International Colloquium on Structural Information and Communication Complexity","first-page":"109","article-title":"Red-blue pebbling with multiple processors: time, communication and memory trade-offs","author":"B\u00f6hnlein","year":"2025"},{"key":"10.1016\/j.ipl.2026.106637_bib0027","series-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","first-page":"1","article-title":"Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication","author":"Kwasniewski","year":"2019"},{"issue":"6","key":"10.1016\/j.ipl.2026.106637_bib0028","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1147\/rd.416.0711","article-title":"Improving the memory-system performance of sparse-matrix vector multiplication","volume":"41","author":"Toledo","year":"1997","journal-title":"IBM J. Res. Dev."},{"issue":"4","key":"10.1016\/j.ipl.2026.106637_bib0029","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1007\/s00224-010-9285-4","article-title":"Optimal sparse matrix dense vector multiplication in the I\/O-model","volume":"47","author":"Bender","year":"2010","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.ipl.2026.106637_bib0030","series-title":"2022 IEEE International Parallel and Distributed Processing Symposium","first-page":"36","article-title":"I\/O-optimal cache-oblivious sparse matrix-sparse matrix multiplication","author":"Gleinig","year":"2022"},{"key":"10.1016\/j.ipl.2026.106637_bib0031","series-title":"Technical Report","article-title":"Sparse Matrix Computations and Their I\/O Complexity","author":"Greiner","year":"2012"},{"key":"10.1016\/j.ipl.2026.106637_bib0032","series-title":"LATIN 2010: Theoretical Informatics: 9th Latin American Symposium, Oaxaca, Mexico, April 19\u201323, 2010. Proceedings 9","first-page":"143","article-title":"The I\/O complexity of sparse matrix dense matrix multiplication","author":"Greiner","year":"2010"},{"key":"10.1016\/j.ipl.2026.106637_bib0033","series-title":"European Symposium on Algorithms","first-page":"750","article-title":"The input\/output complexity of sparse matrix multiplication","author":"Pagh","year":"2014"},{"key":"10.1016\/j.ipl.2026.106637_bib0034","series-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures","first-page":"161","article-title":"Brief announcement: approximating the I\/O complexity of one-shot red-blue pebbling","author":"Carpenter","year":"2016"},{"key":"10.1016\/j.ipl.2026.106637_bib0035","series-title":"Report","article-title":"Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem","author":"Christofides","year":"1976"},{"key":"10.1016\/j.ipl.2026.106637_bib0036","series-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","first-page":"9","article-title":"New approximation algorithms for (1, 2)-TSP","author":"Adamaszek","year":"2018"},{"key":"10.1016\/j.ipl.2026.106637_bib0037","series-title":"Proc. 17th ACM-SIAM Symposium on Discrete Algorithms","first-page":"641","article-title":"8\/7-approximation algorithm for (1,2)-TSP","author":"Berman","year":"2006"},{"issue":"1","key":"10.1016\/j.ipl.2026.106637_bib0038","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","article-title":"The traveling salesman problem with distances one and two","volume":"18","author":"Papadimitriou","year":"1993","journal-title":"Math. Oper. Res."}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000189?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000189?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T04:10:15Z","timestamp":1780027815000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019026000189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":38,"alternative-id":["S0020019026000189"],"URL":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106637","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"I\/O complexity and pebble games with partial computations","name":"articletitle","label":"Article Title"},{"value":"Information Processing Letters","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106637","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"106637"}}