{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T13:56:04Z","timestamp":1762610164380,"version":"3.41.2"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"abstract":"<jats:p>Cumulative memory\u2014the sum of space used per step over the duration of a computation\u2014is a fine-grained measure of time-space complexity that was introduced to analyze cryptographic applications like password hashing. It is a more accurate cost measure for algorithms that have infrequent spikes in memory usage and are run in environments such as cloud computing that allow dynamic allocation and de-allocation of resources during execution, or when many instances of an algorithm are interleaved in parallel.<\/jats:p>\n          <jats:p>We prove the first lower bounds on cumulative memory complexity for both sequential classical computation and quantum circuits. Moreover, we develop general paradigms for bounding cumulative memory complexity inspired by the standard paradigms for proving time-space tradeoff lower bounds that can only lower bound the maximum space used during an execution. The resulting lower bounds on cumulative memory that we obtain are just as strong as the best time-space tradeoff lower bounds, which are very often known to be tight.<\/jats:p>\n          <jats:p>Although previous results for pebbling and random oracle models have yielded time-space tradeoff lower bounds larger than the cumulative memory complexity, our results show that in general computational models such separations cannot follow from known lower bound techniques and are not true for many functions.<\/jats:p>\n          <jats:p>\n            Among many possible applications of our general methods, we show that any classical sorting algorithm with success probability at least 1\/poly(\n            <jats:italic>n<\/jats:italic>\n            ) requires cumulative memory\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"TeX\" version=\"MathJaX\">\\(\\tilde{\\Omega }(n^2) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , any classical matrix multiplication algorithm requires cumulative memory\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>6<\/jats:sup>\n            \/\n            <jats:italic>T<\/jats:italic>\n            ), any quantum sorting circuit requires cumulative memory\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \/\n            <jats:italic>T<\/jats:italic>\n            ), and any quantum circuit that finds\n            <jats:italic>k<\/jats:italic>\n            disjoint collisions in a random function requires cumulative memory\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>T<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3728715","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T11:23:36Z","timestamp":1745407416000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Cumulative Memory Lower Bounds for Randomized and Quantum Computation"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-3545","authenticated-orcid":false,"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, University of Washington, Seattle, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1519-726X","authenticated-orcid":false,"given":"Niels","family":"Kornerup","sequence":"additional","affiliation":[{"name":"Computer Science, The University of Texas at Austin, Austin, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89561"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90014-v"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1821"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a008"},{"key":"e_1_2_1_7_1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Alwen Jo\u00ebl","year":"2016","unstructured":"Jo\u00ebl Alwen and Jeremiah Blocki. 2016. Efficiently Computing Data-Independent Memory-Hard Functions. In Advances in Cryptology \u2013 CRYPTO 2016. Springer, Berlin, Heidelberg, 241\u2013271."},{"key":"e_1_2_1_8_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT","author":"Alwen Jo\u00ebl","year":"2017","unstructured":"Jo\u00ebl Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. 2017. Depth-Robust Graphs and Their Cumulative Memory Complexity. In Advances in Cryptology \u2013 EUROCRYPT 2017. Springer, Cham, 3\u201332."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_13"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56617-7_2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.38"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746622"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9022-9"},{"key":"e_1_2_1_14_1","volume-title":"Block, and Jeremiah Blocki","author":"Ameri Mohammad\u00a0Hassan","year":"2021","unstructured":"Mohammad\u00a0Hassan Ameri, Alexander\u00a0R. Block, and Jeremiah Blocki. 2021. Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes. Cryptology ePrint Archive, Paper 2021\/801. https:\/\/eprint.iacr.org\/2021\/801 https:\/\/eprint.iacr.org\/2021\/801."},{"key":"e_1_2_1_15_1","unstructured":"Andrew Baird Bryant Bost Stefano Buliani Vyom Nagrani Ajay Nair Rahul Popat and Brajendra Singh. 2021. AWS Serverless Multi-Tier Architectures with Amazon API Gateway and AWS Lambda. https:\/\/docs.aws.amazon.com\/whitepapers\/latest\/serverless-multi-tier-architectures-api-gateway-lambda\/welcome.html"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220017"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1778"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.17"},{"key":"e_1_2_1_19_1","unstructured":"Paul Beame and Niels Kornerup. 2023. Cumulative Memory Lower Bounds for Randomized and Quantum Computation. arXiv:2301.05680 \u00a0[cs]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649700"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"volume-title":"Theory of Cryptography","author":"Blocki Jeremiah","key":"e_1_2_1_22_1","unstructured":"Jeremiah Blocki and Samson Zhou. 2017. On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i. In Theory of Cryptography. Springer, Cham, 445\u2013465."},{"key":"e_1_2_1_23_1","volume-title":"Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. In Advances in Cryptology \u2013 ASIACRYPT","author":"Boneh Dan","year":"2016","unstructured":"Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter. 2016. Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. In Advances in Cryptology \u2013 ASIACRYPT 2016. Springer, Berlin, Heidelberg, 220\u2013248."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211022"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90037-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200404"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_28_1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Chen Binyi","year":"2019","unstructured":"Binyi Chen and Stefano Tessaro. 2019. Memory-Hard Functions from Cryptographic Primitives. In Advances in Cryptology \u2013 CRYPTO 2019. Springer, Cham, 543\u2013572."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804032"},{"key":"e_1_2_1_30_1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Dwork Cynthia","year":"2005","unstructured":"Cynthia Dwork, Moni Naor, and Hoeteck Wee. 2005. Pebbling and Proofs of Work. In Advances in Cryptology \u2013 CRYPTO 2005. Springer, Berlin, Heidelberg, 37\u201354."},{"volume-title":"Theory of Cryptography","author":"Dziembowski Stefan","key":"e_1_2_1_31_1","unstructured":"Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. 2011. One-Time Computable Self-erasing Functions. In Theory of Cryptography, Yuval Ishai (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 125\u2013143."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2021.1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.001"},{"key":"e_1_2_1_34_1","volume-title":"Karvelas and Aggelos Kiayias","author":"P.","year":"2014","unstructured":"Nikolaos\u00a0P. Karvelas and Aggelos Kiayias. 2014. Efficient Proofs of Secure Erasure. In Security and Cryptography for Networks, Michel Abdalla and Roberto De\u00a0Prisco (Eds.). Springer International Publishing, Cham, 520\u2013537."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90257-T"},{"key":"e_1_2_1_37_1","first-page":"152","article-title":"On Lower Bounds for Branching Programs","volume":"3","author":"Okol\u2019nishnikova Elizaveta","year":"1993","unstructured":"Elizaveta Okol\u2019nishnikova. 1993. On Lower Bounds for Branching Programs. Siberian Advances in Mathematics 3, 1 (1993), 152\u2013166.","journal-title":"Siberian Advances in Mathematics"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.29"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_11"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780571"},{"key":"e_1_2_1_41_1","volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage E.","unstructured":"John\u00a0E. Savage. 1997. Models of Computation: Exploring the Power of Computing (1st ed.). Addison-Wesley Longman Publishing Co., Inc., USA.","edition":"1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90056-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1977.24"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90029-1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_9"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T11:23:40Z","timestamp":1745407420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,23]]},"references-count":45,"alternative-id":["10.1145\/3728715"],"URL":"https:\/\/doi.org\/10.1145\/3728715","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,4,23]]},"assertion":[{"value":"2024-10-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3728715"}}