{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T01:31:58Z","timestamp":1781659918012,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":16,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384316","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"752-760","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Catalytic approaches to the tree evaluation problem"],"prefix":"10.1145","author":[{"given":"James","family":"Cook","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"Mertz","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Computing Algebraic Formulas Using a Constant Number of Registers","volume":"21","author":"Richard Cleve Michael","year":"1992","unstructured":"Michael Ben-or and Richard Cleve . 1992 . Computing Algebraic Formulas Using a Constant Number of Registers . SIAM J. Comput. 21 , 1 (Feb. 1992 ), 54-58. Michael Ben-or and Richard Cleve. 1992. Computing Algebraic Formulas Using a Constant Number of Registers. SIAM J. Comput. 21, 1 (Feb. 1992 ), 54-58.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the fortysixth annual ACM symposium on Theory of computing. ACM, 857-866","author":"Buhrman Harry","unstructured":"Harry Buhrman , Richard Cleve , Michal Koucky `, Bruno Lof, and Florian Speelman. 2014. Computing with a full memory: catalytic space . In Proceedings of the fortysixth annual ACM symposium on Theory of computing. ACM, 857-866 . Harry Buhrman, Richard Cleve, Michal Koucky`, Bruno Lof, and Florian Speelman. 2014. Computing with a full memory: catalytic space. In Proceedings of the fortysixth annual ACM symposium on Theory of computing. ACM, 857-866."},{"key":"e_1_3_2_1_4_1","first-page":"116","volume-title":"Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62, 1 ( 2018 )","author":"Buhrman Harry","year":"2018","unstructured":"Harry Buhrman , Michal Kouck\u00fd , Bruno Lof , and Florian Speelman . 2018 . Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62, 1 ( 2018 ) , 116 - 135 . Harry Buhrman, Michal Kouck\u00fd, Bruno Lof, and Florian Speelman. 2018. Catalytic Space: Non-determinism and Hierarchy. Theory Comput. Syst. 62, 1 ( 2018 ), 116-135."},{"key":"e_1_3_2_1_5_1","volume-title":"Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms, ESA 2018","volume":"112","author":"Chakraborty Diptarka","year":"2018","unstructured":"Diptarka Chakraborty , Debarati Das , Michal Kouck\u00fd , and Nitin Saurabh . 2018 . Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms, ESA 2018 , August 20-22, 2018, Helsinki, Finland (LIPIcs) , Vol. 112 . 12: 1-12 : 15. Diptarka Chakraborty, Debarati Das, Michal Kouck\u00fd, and Nitin Saurabh. 2018. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland (LIPIcs), Vol. 112. 12: 1-12 : 15."},{"key":"e_1_3_2_1_6_1","volume-title":"Branching Programs: Avoiding Barriers. (","author":"Cook Stephen","year":"2009","unstructured":"Stephen Cook , Mark Braverman , Pierre McKenzie , Rahul Santhanam , and Dustin Wehr . 2009 . Branching Programs: Avoiding Barriers. ( August 2009 ). https:\/\/ www.cs.toronto.edu\/~sacook\/barriers.ps Talk at Barriers Workshop at Princeton . Stephen Cook, Mark Braverman, Pierre McKenzie, Rahul Santhanam, and Dustin Wehr. 2009. Branching Programs: Avoiding Barriers. ( August 2009 ). https:\/\/ www.cs.toronto.edu\/~sacook\/barriers.ps Talk at Barriers Workshop at Princeton."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2077336.2077337"},{"key":"e_1_3_2_1_8_1","volume-title":"Vimal Raj Sharma, and Raghunath Tewari","author":"Datta Samir","year":"2020","unstructured":"Samir Datta , Chetan Gupta , Rahul Jain , Vimal Raj Sharma, and Raghunath Tewari . 2020 . Randomized and Symmetric Catalytic Computation. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ), 24. https:\/\/eccc.weizmann. ac.il\/ report\/2020\/024 Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. 2020. Randomized and Symmetric Catalytic Computation. Electronic Colloquium on Computational Complexity (ECCC) 27 ( 2020 ), 24. https:\/\/eccc.weizmann. ac.il\/ report\/2020\/024"},{"key":"e_1_3_2_1_9_1","volume-title":"33rd Computational Complexity Conference, CCC 2018","volume":"102","author":"Edmonds Jef","year":"2018","unstructured":"Jef Edmonds , Venkatesh Medabalimi , and Toniann Pitassi . 2018 . Hardness of Function Composition for Semantic Read once Branching Programs . In 33rd Computational Complexity Conference, CCC 2018 , June 22-24, 2018, San Diego, CA, USA (LIPIcs) , Vol. 102 . 15: 1-15 : 22. Jef Edmonds, Venkatesh Medabalimi, and Toniann Pitassi. 2018. Hardness of Function Composition for Semantic Read once Branching Programs. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA (LIPIcs), Vol. 102. 15: 1-15 : 22."},{"key":"e_1_3_2_1_10_1","unstructured":"Frank Gray. 1953. Pulse code communication. https:\/\/patents.google.com\/patent\/ US2632058A\/en. US Patent 2632058A.  Frank Gray. 1953. Pulse code communication. https:\/\/patents.google.com\/patent\/ US2632058A\/en. US Patent 2632058A."},{"key":"e_1_3_2_1_11_1","volume-title":"Vimal Raj Sharma, and Raghunath Tewari","author":"Gupta Chetan","year":"2019","unstructured":"Chetan Gupta , Rahul Jain , Vimal Raj Sharma, and Raghunath Tewari . 2019 . Unambiguous Catalytic Computation. Electronic Colloquium on Computational Complexity (ECCC) 26 ( 2019 ), 95. Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. 2019. Unambiguous Catalytic Computation. Electronic Colloquium on Computational Complexity (ECCC) 26 ( 2019 ), 95."},{"key":"e_1_3_2_1_12_1","unstructured":"Michal Kouck\u00fd. 2016. Catalytic computation. Bulletin of the EATCS 118 ( 2016 ).  Michal Kouck\u00fd. 2016. Catalytic computation. Bulletin of the EATCS 118 ( 2016 )."},{"key":"e_1_3_2_1_13_1","unstructured":"David Liu. 2013. Pebbling Arguments for Tree Evaluation. CoRR ( 2013 ).  David Liu. 2013. Pebbling Arguments for Tree Evaluation. CoRR ( 2013 )."},{"key":"e_1_3_2_1_14_1","first-page":"119","volume-title":"Comparative Schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, Jack B. Dennis (Ed.). ACM","author":"Michael","unstructured":"Michael S. Paterson and Carl E. Hewitt. 1970 . Comparative Schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, Jack B. Dennis (Ed.). ACM , New York, NY, USA , 119 - 127 . https:\/\/doi.org\/10.1145\/1344551.1344563 10.1145\/1344551.1344563 Michael S. Paterson and Carl E. Hewitt. 1970. Comparative Schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, Jack B. Dennis (Ed.). ACM, New York, NY, USA, 119-127. https:\/\/doi.org\/10.1145\/1344551.1344563"},{"key":"e_1_3_2_1_15_1","unstructured":"Aaron Potechin. 2016. A Note on Amortized Branching Program Complexity. arXiv:cs.CC\/1611.06632  Aaron Potechin. 2016. A Note on Amortized Branching Program Complexity. arXiv:cs.CC\/1611.06632"},{"key":"e_1_3_2_1_16_1","volume-title":"Tate","author":"Reif John H.","year":"1992","unstructured":"John H. Reif and Stephen R . Tate . 1992 . ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION. John H. Reif and Stephen R. Tate. 1992. ON THRESHOLD CIRCUITS AND POLYNOMIAL COMPUTATION."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384316","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":16,"alternative-id":["10.1145\/3357713.3384316","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384316","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}