Randomized and Symmetric Catalytic Computation

DOI10.1007/978-3-030-50026-9_15MaRDI QIDQ5042242zbMATH OpenOpenAlexFDO

Authors Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

Publication date 19 October 2022

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-50026-9_15

zbMATH Keywords

catalytic computationlogspacerandomized computation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Catalytic space: non-determinism and hierarchy
• Computing with a full memory: catalytic space
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7650313 (Why is no real title available?)
• Symmetric space-bounded computation
• Undirected connectivity in log-space
• Universal traversal sequences with backtracking.

Cited in

(7)

• On pure space vs catalytic space
• Derandomizing logspace with a small shared hard drive
• Almost-catalytic computation
• Derandomizing logspace with a small shared hard drive
• Fully characterizing lossy catalytic computation
• Fully characterizing lossy catalytic computation
• Catalytic computing and register programs beyond log-depth

This page was built for publication: Randomized and Symmetric Catalytic Computation

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