{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T18:58:41Z","timestamp":1779303521533,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T00:00:00Z","timestamp":1758499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n We obtain new catalytic algorithms for space-bounded derandomization. In the catalytic computation model introduced by (Buhrman, Cleve, Kouck\u00fd, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. We prove that\n \n \n $$BPSPACE[S] \\subseteq CSPACE[{S},{S^2}]$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n P<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n S<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n \u2286<\/mml:mo>\n C<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n S<\/mml:mi>\n ,<\/mml:mo>\n \n S<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n where\n \n \n $$BPSPACE[S]$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n P<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n [<\/mml:mo>\n S<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n corresponds to randomized space\n S<\/jats:italic>\n computation, and\n \n \n $$CSPACE[{S},{C}]$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/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 corresponds to catalytic algorithms that use\n O(S)<\/jats:italic>\n bits of workspace and\n O(C)<\/jats:italic>\n bits of catalytic space. Previously, only\n \n \n $$BPSPACE[S]\\subseteq CSPACE[{S},{2^{O(S)}}]$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n P<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n S<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n \u2286<\/mml:mo>\n C<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n S<\/mml:mi>\n ,<\/mml:mo>\n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n was known. In fact, we prove a general tradeoff, that for every\n \n \n $$\\alpha \\in [1,1.5]$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 1.5<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$BPSPACE[S] \\subseteq CSPACE[{S^{\\alpha}},{S^{3-\\alpha}}].$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n P<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n S<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n \u2286<\/mml:mo>\n C<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n \n [<\/mml:mo>\n \n S<\/mml:mi>\n \u03b1<\/mml:mi>\n <\/mml:msup>\n ,<\/mml:mo>\n \n S<\/mml:mi>\n \n 3<\/mml:mn>\n -<\/mml:mo>\n \u03b1<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n ]<\/mml:mo>\n <\/mml:mrow>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n We do not use the algebraic techniques of prior work on catalytic computation. Instead, we develop an algorithm that branches based on if the catalytic tape is conditionally random, and instantiate this primitive in a recursive framework. Our result gives an alternate proof of the best known time-space tradeoff for\n \n \n $$BPSPACE[S]$$<\/jats:tex-math>\n \n \n B<\/mml:mi>\n P<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n [<\/mml:mo>\n S<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , due to (Cai, Chakaravarthy, and van Melkebeek, Theory Comput. Sys. 2006). As a final application, we extend our results to solve search problems in\n \n \n $$CSPACE[{S},{S^2}]$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n S<\/mml:mi>\n P<\/mml:mi>\n A<\/mml:mi>\n C<\/mml:mi>\n E<\/mml:mi>\n [<\/mml:mo>\n S<\/mml:mi>\n ,<\/mml:mo>\n \n S<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . As far as we are aware, this constitutes the first study of search problems in the catalytic computing model.\n <\/jats:p>","DOI":"10.1007\/s00037-025-00275-6","type":"journal-article","created":{"date-parts":[[2025,9,22]],"date-time":"2025-09-22T13:12:53Z","timestamp":1758546773000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Derandomizing Logspace With a Small Shared Hard Drive"],"prefix":"10.1007","volume":"34","author":[{"given":"Edward","family":"Pyne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,22]]},"reference":[{"key":"275_CR1","doi-asserted-by":"crossref","unstructured":"Dimitris Achlioptas (2003). Database-friendly random projections:\nJohnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4),\n671\u2013687. URL https:\/\/doi.org\/10.1016\/S0022-0000(03)00025-4.","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"275_CR2","doi-asserted-by":"crossref","unstructured":"Sagar Bisoyi, Krishnamoorthy Dinesh & Jayalal Sarma (2022).\nOn pure space vs catalytic space. Theor. Comput. Sci. 921, 112\u2013126. URL https:\/\/doi.org\/10.1016\/j.tcs.2022.04.005.","DOI":"10.1016\/j.tcs.2022.04.005"},{"key":"275_CR3","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Richard Cleve, Michal Kouck\u00dd, Bruno Loff\n& Florian Speelman (2014). Computing with a full memory: catalytic\nspace. In Symposium on Theory of Computing, STOC 2014, 857\u2013\n866. ACM.","DOI":"10.1145\/2591796.2591874"},{"key":"275_CR4","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Michal Kouck\u00dd, Bruno Loff & Florian\nSpeelman (2018). Catalytic Space: Non-determinism and Hierarchy.\nTheory Comput. Syst. 62(1), 116\u2013135. URL https:\/\/doi.org\/10.1007\/s00224-017-9784-7.","DOI":"10.1007\/s00224-017-9784-7"},{"key":"275_CR5","doi-asserted-by":"crossref","unstructured":"Jin-yi Cai, Venkatesan T. Chakaravarthy & Dieter van\nMelkebeek (2006). Time-Space Tradeoff in Derandomizing Probabilistic\nLogspace. Theory Comput. Syst. 39(1), 189\u2013208. URL https:\/\/doi.org\/10.1007\/s00224-005-1264-9.","DOI":"10.1007\/s00224-005-1264-9"},{"key":"275_CR6","doi-asserted-by":"crossref","unstructured":"Kuan Cheng & William M. Hoza (2022). Hitting Sets Give Two-\nSided Derandomization of Small Space. Theory of Computing 18(21),\n1\u201332. URL https:\/\/theoryofcomputing.org\/articles\/v018a021.","DOI":"10.4086\/toc.2022.v018a021"},{"key":"275_CR7","doi-asserted-by":"crossref","unstructured":"Gil Cohen, Dean Doron, Ori Sberlo & Amnon Ta-Shma (2023).\nApproximating Iterated Multiplication of Stochastic Matrices in Small\nSpace. In Proceedings of the 55th Annual ACM Symposium on Theory\nof Computing, STOC 2023, 35\u201345. ACM.","DOI":"10.1145\/3564246.3585181"},{"key":"275_CR8","unstructured":"James Cook, Jiatu Li, Ian Mertz & Edward Pyne (2024). The\nStructure of Catalytic Space: Capturing Randomness and Time via\nCompression. Electron. Colloquium Comput. Complex. TR24-106."},{"key":"275_CR9","doi-asserted-by":"crossref","unstructured":"James Cook & Ian Mertz (2020). Catalytic approaches to the tree\nevaluation problem. In Proccedings of the 52nd Annual ACM SIGACT\nSymposium on Theory of Computing, STOC 2020, 752\u2013760. ACM.","DOI":"10.1145\/3357713.3384316"},{"key":"275_CR10","doi-asserted-by":"crossref","unstructured":"James Cook & Ian Mertz (2024). Tree Evaluation Is in Space O(log\nn \u00b7 log log n). In Proceedings of the 56th Annual ACM Symposium\non Theory of Computing, STOC 2024, Vancouver, BC, Canada, June\n24-28, 2024, Bojan Mohar, Igor Shinkar & Ryan O\u2019Donnell,\neditors, 1268\u20131278. ACM.","DOI":"10.1145\/3618260.3649664"},{"key":"275_CR11","doi-asserted-by":"crossref","unstructured":"Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma\n& Raghunath Tewari (2020). Randomized and Symmetric Catalytic\nComputation. In Computer Science - Theory and Applications - 15th\nInternational Computer Science Symposium in Russia, CSR 2020, 211\u2013\n223. Springer.","DOI":"10.1007\/978-3-030-50026-9_15"},{"key":"275_CR12","doi-asserted-by":"crossref","unstructured":"Dean Doron, Edward Pyne & Roei Tell (2024). Opening Up\nthe Distinguisher: A Hardness to Randomness Approach for BPL=L\nThat Uses Properties of BPL. In Proceedings of the 56th Annual ACM\nSymposium on Theory of Computing, STOC 2024, Vancouver, BC,\nCanada, June 24-28, 2024, Bojan Mohar, Igor Shinkar & Ryan\nO\u2019Donnell, editors, 2039\u20132049. ACM. URL https:\/\/doi.org\/10.1145\/3618260.3649772.","DOI":"10.1145\/3618260.3649772"},{"key":"275_CR13","unstructured":"Chetan Gupta, Rahul Jain, Vimal Raj Sharma & Raghunath\nTewari (2019). Unambiguous Catalytic Computation. In 39th IARCS\nAnnual Conference on Foundations of Software Technology and Theoretical\nComputer Science, FSTTCS 2019, volume 150 of LIPIcs, 16:1\u2013\n16:13."},{"key":"275_CR14","doi-asserted-by":"crossref","unstructured":"Daniel M. Kane, Raghu Meka & Jelani Nelson (2011). Almost\nOptimal Explicit Johnson-Lindenstrauss Families. In Approximation,\nRandomization, and Combinatorial Optimization. Algorithms and Techniques\n- 14th International Workshop, APPROX 2011, and 15th International\nWorkshop, RANDOM 2011, Princeton, NJ, USA, August\n17-19, 2011. Proceedings, Leslie Ann Goldberg, Klaus Jansen,\nR. Ravi & Jos\u00c9 D. P. Rolim, editors, volume 6845 of Lecture Notes\nin Computer Science, 628\u2013639. Springer. URL https:\/\/doi.org\/10.1007\/978-3-642-22935-0_53.","DOI":"10.1007\/978-3-642-22935-0_53"},{"key":"275_CR15","doi-asserted-by":"crossref","unstructured":"Daniel M. Kane & Jelani Nelson (2014). Sparser Johnson-\nLindenstrauss Transforms. J. ACM 61(1), 4:1\u20134:23.","DOI":"10.1145\/2559902"},{"key":"275_CR16","doi-asserted-by":"crossref","unstructured":"Jiatu Li, Edward Pyne & Roei Tell (2024). Distinguishing, Predicting,\nand Certifying: On the Long Reach of Partial Notions of\nPseudorandomness. In 65th IEEE Annual Symposium on Foundations\nof Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30,\n2024, 1\u201313. IEEE.","DOI":"10.1109\/FOCS61266.2024.00095"},{"key":"275_CR17","unstructured":"Ian Mertz (2023). Reusing Space: Techniques and Open Problems.\nBulletin of EATCS 141(3)."},{"key":"275_CR18","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1990). Psuedorandom Generators for Space-Bounded\nComputation. In Proceedings of the 22nd Annual ACM Symposium on\nTheory of Computing, May 13-17, 1990, Baltimore, Maryland, USA,\nHarriet Ortiz, editor, 204\u2013212. ACM. URL https:\/\/doi.org\/10.1145\/100216.100242.","DOI":"10.1145\/100216.100242"},{"key":"275_CR19","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1993). On Read-Once vs. Multiple Access to Randomness\nin Logspace. Theor. Comput. Sci. 107(1), 135\u2013144. URL https:\/\/doi.org\/10.1016\/0304-3975(93)90258-U.","DOI":"10.1016\/0304-3975(93)90258-U"},{"key":"275_CR20","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1994). RL \u00a1= SC. Comput. Complex. 4, 1\u201311. URL https:\/\/doi.org\/10.1007\/BF01205052.","DOI":"10.1007\/BF01205052"},{"key":"275_CR21","doi-asserted-by":"crossref","unstructured":"Aaron (Louie) Putterman & Edward Pyne (2023). Near-Optimal\nDerandomization of Medium-Width Branching Programs. In Proceedings\nof the 55th Annual ACM Symposium on Theory of Computing,\nSTOC 2023, 23\u201334.","DOI":"10.1145\/3564246.3585108"},{"key":"275_CR22","doi-asserted-by":"crossref","unstructured":"Edward Pyne, Ran Raz & Wei Zhan (2023). Certified Hardness\nvs. Randomness for Log-Space. In 64th IEEE Annual Symposium on\nFoundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA,\nNovember 6-9, 2023, 989\u20131007. IEEE. URL https:\/\/doi.org\/10.1109\/FOCS57990.2023.00061.","DOI":"10.1109\/FOCS57990.2023.00061"},{"key":"275_CR23","doi-asserted-by":"crossref","unstructured":"Michael E. Saks & Shiyu Zhou (1999).$$BP_HSpace(S) \\subseteq DSPACE(S^{3\/2})$$. J. Comput. Syst. Sci. 58(2), 376\u2013403. URL https:\/\/doi.org\/10.1006\/jcss.1998.1616.","DOI":"10.1006\/jcss.1998.1616"},{"key":"275_CR24","doi-asserted-by":"crossref","unstructured":"D. Sivakumar (2002). Algorithmic derandomization via complexity\ntheory. In Proceedings on 34th Annual ACM Symposium on Theory\nof Computing, May 19-21, 2002, Montr\u00e9al, Qu\u00e9bec, Canada,\nJohn H. Reif, editor, 619\u2013626. ACM. URL https:\/\/doi.org\/10.1145\/509907.509996.","DOI":"10.1145\/509907.509996"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00275-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00275-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00275-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T10:32:39Z","timestamp":1767004359000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00275-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["275"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00275-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,22]]},"assertion":[{"value":"24 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"13"}}