Catalytic computation

MaRDI QIDQ4967204zbMATH OpenFDO

Authors Michal Koucký

Publication date 3 July 2019

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/400/380

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computing with a full memory: catalytic space
• Catalytic space: non-determinism and hierarchy
• scientific article; zbMATH DE number 6829365
• Mathematical Foundations of Computer Science 2003
• Memoryless computation: new results, constructions, and extensions

Cited in

(16)

• Catalytic space: non-determinism and hierarchy
• Catalytic transformations with CNOT gate
• Power of uninitialized qubits in shallow quantum circuits
• Frameworks for designing in-place graph algorithms
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Memoryless computation: new results, constructions, and extensions
• A framework for in-place graph algorithms
• Optimal In-place Algorithms for Basic Graph Problems
• Computing with a full memory: catalytic space
• On pure space vs catalytic space
• On pure space vs catalytic space
• Reusing space: techniques and open problems
• Almost-catalytic computation
• Unambiguous, randomized, and symmetric catalytic computation
• Fully characterizing lossy catalytic computation
• Catalytic computing and register programs beyond log-depth

This page was built for publication: Catalytic computation

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