{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:02:33Z","timestamp":1773230553372,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional\n                    <jats:italic toggle=\"yes\">auxiliary<\/jats:italic>\n                    tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This article, studies the power of some natural variants of catalytic Turing machines with\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\log n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {CBPL}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is contained in the class\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {ZPP}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful.\n                  <\/jats:p>","DOI":"10.1145\/3774644","type":"journal-article","created":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T12:15:06Z","timestamp":1763381706000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Unambiguous, Randomized, and Symmetric Catalytic Computation"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2196-2308","authenticated-orcid":false,"given":"Samir","family":"Datta","sequence":"first","affiliation":[{"name":"Chennai Mathematical Institute","place":["Chennai, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0727-160X","authenticated-orcid":false,"given":"Chetan","family":"Gupta","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Roorkee","place":["Roorkee, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8567-9475","authenticated-orcid":false,"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Siegen","place":["Siegen, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6086-5999","authenticated-orcid":false,"given":"Vimal","family":"Sharma","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Jodhpur","place":["Jodhpur, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1522-8561","authenticated-orcid":false,"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur","place":["Kanpur, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,23]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1646"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0280-6"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.04.005"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591874"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9784-7"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718112"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384316"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.8"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649664"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2025.50"},{"key":"e_1_3_1_13_2","first-page":"138","article-title":"Nonuniform catalytic space and the direct sum for space","volume":"22","author":"Girard Vincent","year":"2015","unstructured":"Vincent Girard, Michal Kouck\u00fd, and Pierre McKenzie. 2015. Nonuniform catalytic space and the direct sum for space. Electronic Colloquium on Computational Complexity 22 (2015), 138. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2015\/138","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_3_1_14_2","unstructured":"Chetan Gupta Rahul Jain Vimal Raj Sharma and Raghunath Tewari. 2024. Lossy Catalytic Computation. Retrieved from https:\/\/arxiv.org\/abs\/2408.14670"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_1_17_2","article-title":"Catalytic computation","volume":"118","author":"Kouck\u00fd Michal","year":"2016","unstructured":"Michal Kouck\u00fd. 2016. Catalytic computation. Bulletin of EATCS 118 (2016). Retrieved from http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/400","journal-title":"Bulletin of EATCS"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00023-5"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"e_1_3_1_20_2","article-title":"Reusing Space: Techniques and Open Problems","volume":"141","author":"Mertz Ian","year":"2023","unstructured":"Ian Mertz. 2023. Reusing Space: Techniques and Open Problems. Bulletin of EATCS 141 (2023). Retrieved from http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/780","journal-title":"Bulletin of EATCS"},{"key":"e_1_3_1_21_2","volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917)","author":"Potechin Aaron","year":"2017","unstructured":"Aaron Potechin. 2017. A note on amortized branching program complexity. In Proceedings of the 32nd Computational Complexity Conference (CCC\u201917). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, Article 4, 12 pages."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T15:20:53Z","timestamp":1773156053000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,23]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3774644"],"URL":"https:\/\/doi.org\/10.1145\/3774644","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,23]]},"assertion":[{"value":"2024-02-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}