{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:46:57Z","timestamp":1782265617143,"version":"3.54.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T00:00:00Z","timestamp":1779235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T00:00:00Z","timestamp":1779235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL program."},{"name":"Royal Society University Research Fellowship","award":["URF\\R1\\191059"],"award-info":[{"award-number":["URF\\R1\\191059"]}]},{"name":"Divide and Quantum of the program \u2018NWA-ORC\u2019, which is partly funded by the Dutch Research Council","award":["NWA.1389.20.241"],"award-info":[{"award-number":["NWA.1389.20.241"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n A\n catalytic machine<\/jats:italic>\n is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, \u201ccatalytic\u201d tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as\n catalytic logspace<\/jats:italic>\n (\n \n \n $${\\textsf {CL}} $$<\/jats:tex-math>\n \n CL<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ), can compute problems which are believed to be impossible for\n \n \n $$\\textsf {L} $$<\/jats:tex-math>\n \n L<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined\n lossy catalytic logspace<\/jats:italic>\n (\n \n \n $${\\textsf {LCL}} [e]$$<\/jats:tex-math>\n \n \n LCL<\/mml:mi>\n [<\/mml:mo>\n e<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) as a variant of\n \n \n $${\\textsf {CL}} $$<\/jats:tex-math>\n \n CL<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n where we allow up to\n e<\/jats:italic>\n errors when resetting the catalytic tape. They showed that\n \n \n $${\\textsf {LCL}} [e] = {\\textsf {CL}} $$<\/jats:tex-math>\n \n \n LCL<\/mml:mi>\n [<\/mml:mo>\n e<\/mml:mi>\n ]<\/mml:mo>\n =<\/mml:mo>\n CL<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for any\n \n \n $$e = O(1)$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , which remains the frontier of our understanding. In this work we completely characterize lossy catalytic space (\n \n \n $${\\textsf {LCSPACE}} [s,c,e]$$<\/jats:tex-math>\n \n \n LCSPACE<\/mml:mi>\n [<\/mml:mo>\n s<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n ,<\/mml:mo>\n e<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) in terms of ordinary catalytic space (\n \n \n $${\\textsf {CSPACE}} [s,c]$$<\/jats:tex-math>\n \n \n CSPACE<\/mml:mi>\n [<\/mml:mo>\n s<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ). We show that\n \n \n $$\\begin{aligned} {\\textsf {LCSPACE}} [s,c,e] = {\\textsf {CSPACE}} [\\Theta (s + e \\log c), \\Theta (c)] \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n LCSPACE<\/mml:mi>\n [<\/mml:mo>\n s<\/mml:mi>\n ,<\/mml:mo>\n c<\/mml:mi>\n ,<\/mml:mo>\n e<\/mml:mi>\n ]<\/mml:mo>\n =<\/mml:mo>\n CSPACE<\/mml:mi>\n [<\/mml:mo>\n \u0398<\/mml:mi>\n (<\/mml:mo>\n s<\/mml:mi>\n +<\/mml:mo>\n e<\/mml:mi>\n log<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n \u0398<\/mml:mi>\n (<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n In other words, allowing\n e<\/jats:italic>\n errors on a catalytic tape of length\n c<\/jats:italic>\n is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional\n \n \n $$e \\log c$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n log<\/mml:mo>\n c<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n bits of ordinary working memory. As a consequence, we show that for any\n e<\/jats:italic>\n ,\n \n \n $${\\textsf {LCL}} [e] = {\\textsf {CL}} $$<\/jats:tex-math>\n \n \n LCL<\/mml:mi>\n [<\/mml:mo>\n e<\/mml:mi>\n ]<\/mml:mo>\n =<\/mml:mo>\n CL<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n implies\n \n \n $${\\textsf {SPACE}} [e \\log n] \\subseteq {\\textsf {ZPP}} $$<\/jats:tex-math>\n \n \n SPACE<\/mml:mi>\n [<\/mml:mo>\n e<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n \u2286<\/mml:mo>\n ZPP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , thus giving a barrier to any improvement beyond\n \n \n $${\\textsf {LCL}} [O(1)] = {\\textsf {CL}} $$<\/jats:tex-math>\n \n \n LCL<\/mml:mi>\n [<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n ]<\/mml:mo>\n =<\/mml:mo>\n CL<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We also extend all our results to every variant of catalytic space.\n <\/jats:p>","DOI":"10.1007\/s00453-026-01376-6","type":"journal-article","created":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T07:20:40Z","timestamp":1779261640000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fully Characterizing Lossy Catalytic Computation"],"prefix":"10.1007","volume":"88","author":[{"given":"Marten","family":"Folkertsma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"Mertz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Speelman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quinten","family":"Tupker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,20]]},"reference":[{"key":"1376_CR1","unstructured":"Agarwala, A., Mertz, I.: In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 2025"},{"key":"1376_CR2","doi-asserted-by":"publisher","unstructured":"Buhrman, H., Cleve, R., Kouck\u00fd, M., Loff, B., Speelman, F.: Computing with a full memory: catalytic space. In ACM Symposium on Theory of Computing (STOC), pages 857\u2013866, (2014). https:\/\/doi.org\/10.1145\/2591796.2591874","DOI":"10.1145\/2591796.2591874"},{"key":"1376_CR3","doi-asserted-by":"publisher","unstructured":"Buhrman, H., Folkertsma, M., Mertz, I., Speelman, F., Strelchuk, S., Subramanian, S., Tupker, Q.: Quantum catalytic space. In TQC, volume 350 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1\u201311:24. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2025. https:\/\/doi.org\/10.4230\/LIPICS.TQC.2025.11","DOI":"10.4230\/LIPICS.TQC.2025.11"},{"key":"1376_CR4","doi-asserted-by":"crossref","unstructured":"Bisoyi, S., Dinesh, K., Rai, B.\u00a0D., Sarma, J.: Almost-catalytic and property-catalytic computation, (2024)","DOI":"10.1007\/978-3-031-92935-9_3"},{"key":"1376_CR5","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/J.TCS.2022.04.005","volume":"921","author":"S Bisoyi","year":"2022","unstructured":"Bisoyi, S., Dinesh, K., Sarma, J.: On pure space vs catalytic space. Theoretical Computer Science (TCS) 921, 112\u2013126 (2022). https:\/\/doi.org\/10.1016\/J.TCS.2022.04.005","journal-title":"Theoretical Computer Science (TCS)"},{"key":"1376_CR6","volume-title":"Florian Speelman","author":"H Buhrman","year":"2025","unstructured":"Buhrman, H., Folkertsma, M., Mertz, I.: Florian Speelman. Sathya Subramanian, and Quinten Tupker. Quantum catalytic computation, Sergii Strelchuk (2025)"},{"issue":"1","key":"1376_CR7","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/S00224-017-9784-7","volume":"62","author":"H Buhrman","year":"2018","unstructured":"Buhrman, H., Kouck\u00fd, M., Loff, B., Speelman, F.: Catalytic space: Non-determinism and hierarchy. Theory of Computing Systems (TOCS) 62(1), 116\u2013135 (2018). https:\/\/doi.org\/10.1007\/S00224-017-9784-7","journal-title":"Theory of Computing Systems (TOCS)"},{"issue":"4","key":"1376_CR8","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A Borodin","year":"1977","unstructured":"Borodin, A.: On relating time and space to size and depth. SIAM J. Comput. 6(4), 733\u2013744 (1977). https:\/\/doi.org\/10.1137\/0206054","journal-title":"SIAM J. Comput."},{"key":"1376_CR9","doi-asserted-by":"crossref","unstructured":"Bose, R.\u00a0C., Ray-Chaudhuri, D.\u00a0K.: On a class of error correcting binary group codes. Information and control, 3(1):68\u201379, (1960)","DOI":"10.1016\/S0019-9958(60)90287-4"},{"key":"1376_CR10","doi-asserted-by":"crossref","unstructured":"Cook, J., Li, J., Mertz, I., Pyne, E.: The structure of catalytic space: In ACM Symposium on Theory of Computing (STOC), pages 554\u2013564. Association for Computing Machinery (ACM), 2025","DOI":"10.1145\/3717823.3718112"},{"key":"1376_CR11","doi-asserted-by":"publisher","unstructured":"Cook, J., Mertz, I.: Catalytic approaches to the tree evaluation problem. In ACM Symposium on Theory of Computing (STOC), pages 752\u2013760. ACM, (2020). https:\/\/doi.org\/10.1145\/3357713.3384316","DOI":"10.1145\/3357713.3384316"},{"key":"1376_CR12","unstructured":"Cook, J., Mertz, I.: Encodings and the tree evaluation problem. Electronic Colloquium on Computational Complexity (ECCC), TR21-054, (2021). URL: https:\/\/eccc.weizmann.ac.il\/report\/2021\/054"},{"key":"1376_CR13","doi-asserted-by":"publisher","unstructured":"Cook, J., Mertz, I.: Trading time and space in catalytic branching programs. In IEEE Conference on Computational Complexity (CCC), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1\u20138:21, (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2022.8","DOI":"10.4230\/LIPIcs.CCC.2022.8"},{"key":"1376_CR14","doi-asserted-by":"publisher","unstructured":"Cook, J., Mertz, I.: Tree evaluation is in space O(log n $$\\cdot $$ log log n). SIAM Journal on Computing (SICOMP), Special Section STOC 2024:130\u2013160, 2025. https:\/\/doi.org\/10.1137\/24M1690126","DOI":"10.1137\/24M1690126"},{"key":"1376_CR15","doi-asserted-by":"publisher","unstructured":"Datta, S., Gupta, C., Jain, R., Sharma, V.\u00a0R., Tewari, R.: Randomized and symmetric catalytic computation. In CSR, volume 12159 of Lecture Notes in Computer Science (LNCS), pages 211\u2013223. Springer, (2020). https:\/\/doi.org\/10.1007\/978-3-030-50026-9_15","DOI":"10.1007\/978-3-030-50026-9_15"},{"key":"1376_CR16","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Syndrome encoding and decoding of bch codes in sublinear time, (2006). URL: https:\/\/www.cs.bu.edu\/~reyzin\/code\/bch-excerpt.pdf"},{"key":"1376_CR17","doi-asserted-by":"crossref","unstructured":"Doron, D., Pyne, E., Tell, R.: Opening up the distinguisher: A hardness to randomness approach for BPL = L that uses properties of BPL. In Proceedings of the 56nd Annual ACM Symposium on Theory of Computing, STOC 2024, pages 2039\u20132049, (2024)","DOI":"10.1145\/3618260.3649772"},{"key":"1376_CR18","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Advances in Cryptology - EUROCRYPT 2004, (2004)","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"1376_CR19","unstructured":"Dulek, Y.: Catalytic space: on reversibility and multiple-access randomness, private communication (2015)"},{"key":"1376_CR20","unstructured":"Folkertsma, M., Mertz, I., Speelman, F., Tupker, Q.: Fully characterizing lossy catalytic computation. In Innovations in Theoretical Computer Science Conference (ITCS), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1\u201350:13, (2025)"},{"key":"1376_CR21","doi-asserted-by":"publisher","unstructured":"Gupta, C., Jain, R., Sharma, V.\u00a0R., Tewari, R.: Unambiguous catalytic computation. In Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 150 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1\u201316:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019) https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.16","DOI":"10.4230\/LIPIcs.FSTTCS.2019.16"},{"key":"1376_CR22","unstructured":"Gupta, C., Jain, R., Sharma, V.\u00a0R., Tewari, R.: Lossy catalytic computation. Computing Research Repository (CoRR), abs\/2408.14670, (2024)"},{"key":"1376_CR23","first-page":"147","volume":"2","author":"A Hocquenghem","year":"1959","unstructured":"Hocquenghem, A.: Codes correcteurs d\u2019erreurs. Chiffers 2, 147\u2013156 (1959)","journal-title":"Codes correcteurs d\u2019erreurs. Chiffers"},{"key":"1376_CR24","doi-asserted-by":"crossref","unstructured":"Kouck\u00fd, M., Mertz, I., Pyne, T., Sami, S.: Collapsing catalytic classes. In IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 2025","DOI":"10.1109\/FOCS63196.2025.00025"},{"key":"1376_CR25","unstructured":"Kouck\u00fd, M.: Catalytic computation. Bulletin of the EATCS (B.EATCS), 118, (2016)"},{"issue":"2","key":"1376_CR26","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1006\/jcss.1999.1672","volume":"60","author":"K-J Lange","year":"2000","unstructured":"Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. J. Comput. Syst. Sci. 60(2), 354\u2013367 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"1376_CR27","doi-asserted-by":"publisher","unstructured":"Li, J., Pyne, E., Tell, R.: Distinguishing, predicting, and certifying: Computational Complexity (CC), 34(2):13, 2025. https:\/\/doi.org\/10.1007\/S00037-025-00275-6","DOI":"10.1007\/S00037-025-00275-6"},{"key":"1376_CR28","unstructured":"Mertz, I.: Reusing space: Techniques and open problems. Bulletin of the EATCS (B.EATCS), 141:57\u2013106, (2023)"},{"key":"1376_CR29","doi-asserted-by":"publisher","unstructured":"Potechin, A.: A note on amortized branching program complexity. In IEEE Conference on Computational Complexity (CCC), volume\u00a079 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1\u20134:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.4","DOI":"10.4230\/LIPIcs.CCC.2017.4"},{"key":"1376_CR30","unstructured":"Pyne, E.: Derandomizing logspace with a small shared hard drive. In 39th Computational Complexity Conference, CCC 2024, volume 300 of LIPIcs, pages 4:1\u20134:20, (2024)"},{"key":"1376_CR31","doi-asserted-by":"publisher","unstructured":"Robere, R., Zuiddam, J.: Amortized circuit complexity, formal complexity measures, and catalytic algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 759\u2013769. IEEE, (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00079","DOI":"10.1109\/FOCS52979.2021.00079"},{"key":"1376_CR32","doi-asserted-by":"publisher","unstructured":"Williams, R.: Simulating time in square-root space. In ACM Symposium on Theory of Computing (STOC), pages 13\u201323. Association for Computing Machinery (ACM), 2025.https:\/\/doi.org\/10.1145\/3717823.3718225","DOI":"10.1145\/3717823.3718225"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01376-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01376-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01376-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:11:02Z","timestamp":1782263462000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01376-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,20]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1376"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01376-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,20]]},"assertion":[{"value":"25 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"46"}}