Fully characterizing lossy catalytic computation

DOI10.1007/S00453-026-01376-6MaRDI QIDQ7255556zbMATH OpenFDO

Authors Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

Publication date 1 June 2026

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-026-01376-6

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A note on amortized branching program complexity
• Advances in Cryptology - EUROCRYPT 2004
• Amortized circuit complexity, formal complexity measures, and catalytic algorithms
• Catalytic approaches to the tree evaluation problem
• Catalytic computation
• Catalytic space: non-determinism and hierarchy
• Computing with a full memory: catalytic space
• Derandomizing logspace with a small shared hard drive
• Derandomizing logspace with a small shared hard drive
• scientific article; zbMATH DE number 3147923 (Why is no real title available?)
• scientific article; zbMATH DE number 7650313 (Why is no real title available?)
• On a class of error correcting binary group codes
• On pure space vs catalytic space
• On Relating Time and Space to Size and Depth
• Randomized and Symmetric Catalytic Computation
• Reusing space: techniques and open problems
• Reversible space equals deterministic space
• Trading time and space in catalytic branching programs

This page was built for publication: Fully characterizing lossy catalytic computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7255556)