Lossy Catalytic Computation

doi:10.1145/828.1884

M. L. Fredman, J. Komlós, E. Szemerédi, Storing a sparse table with 0(1) worst case access time, Vol. 31, ACM, NY, USA, 1984, pp. 538–544 · 1984

Earlier work this paper cites.

doi:10.1145/2591796.2591874

H. Buhrman, R. Cleve, M. Koucký, B. Loff, F. Speelman, Computing with a full memory: Catalytic space, in: 46th Annual ACM Symposium on Theory of Computing, STOC, ACM, NY, USA, 2014 · 2014

Earlier work this paper cites.

P. M. Vincent Girard, Michal Koucký, Nonuniform catalytic space and the direct sum for space , Vol. 22, 2015, p. 138. URL http://eccc.hpi-web.de/report/2015/138

2015

Earlier work this paper cites.

doi:10.4230/LIPIcs.CCC.2017.4

A. Potechin, A note on amortized branching program complexity, in: 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, 2017 · 2017

Earlier work this paper cites.

doi:10.1007/s00224-017-9784-7

H. Buhrman, M. Koucký, B. Loff, F. Speelman, Catalytic space: Non-determinism and hierarchy, Vol. 62, 2018, pp. 116–135 · 2018

Earlier work this paper cites.

doi:10.4230/LIPIcs.FSTTCS.2019.16

C. Gupta, R. Jain, V. R. Sharma, R. Tewari, Unambiguous Catalytic Computation, in: FSTTCS 2019, 2019, pp. 16:1–16:13 · 2019

Cited alongside, same era.

doi:10.1145/3357713.3384316

J. Cook, I. Mertz, Catalytic approaches to the tree evaluation problem, in: 52nd Annual ACM Symposium on Theory of Computing, STOC, Chicago, IL, USA, ACM, 2020, pp. 752–760 · 2020

Cited alongside, same era.

doi:10.1007/978-3-030-50026-9\_15

S. Datta, C. Gupta, R. Jain, V. R. Sharma, R. Tewari, Randomized and symmetric catalytic computation, in: 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, 2020 · 2020

Cited alongside, same era.

doi:10.1007/978-3-030-59267-7\_37

S. Bisoyi, K. Dinesh, J. Sarma, On pure space vs catalytic space, in: Theory and Applications of Models of Computation, 16th International Conference, TAMC, Changsha, China, 2020 · 2020

Cited alongside, same era.

M. Koucký, Catalytic computation , Bull. EATCS 118. URL http://eatcs.org/beatcs/index.php/beatcs/article/view/400

Cited in the paper.

arXiv:TR21-054

J. Cook, I. Mertz, Encodings and the tree evaluation problem , Electron. Colloquium Comput. Complex. TR21-054 · 2021

Later among the works it cites.

doi:10.4230/LIPICS.CCC.2022.8

J. Cook, I. Mertz, Trading time and space in catalytic branching programs , in: S. Lovett (Ed.), 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, Vol. 234 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 8:1–8:21 · 2022

Later among the works it cites.

doi:10.1145/3618260.3649664

J. Cook, I. Mertz, Tree evaluation is in space o(log n ⋅ \cdot log log n) , in: B. Mohar, I. Shinkar, R. O’Donnell (Eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, ACM, 2024, pp. 1268–1278 · 2024

Closest in time.

doi:10.4230/LIPICS.CCC.2024.4

E. Pyne, Derandomizing logspace with a small shared hard drive , in: R. Santhanam (Ed.), 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA, Vol. 300 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, pp. 4:1–4:20 · 2024

Closest in time.