Time/Space Trade-Offs for Reversible Computation
From MaRDI portal
Publication:3832041
DOI10.1137/0218053zbMath0676.68010OpenAlexW2061073612MaRDI QIDQ3832041
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/500470befb771a5cb10095103f50b4cda75ff008
Related Items (73)
Computability and complexity of ray tracing ⋮ Improved Quantum Circuits for Elliptic Curve Discrete Logarithms ⋮ Low-gate quantum golden collision finding ⋮ The complexity of reversible cellular automata ⋮ Static-memory-hard functions, and modeling the cost of space vs. time ⋮ An unambiguous class possessing a complete set ⋮ LESS is More: Code-Based Signatures Without Syndromes ⋮ Efficient and exact quantum compression ⋮ Improved reversible and quantum circuits for Karatsuba-based integer multiplication. ⋮ The stochastic thermodynamics of computation ⋮ Algorithmic arguments in physics of computation ⋮ Simpler constructions of asymmetric primitives from obfuscation ⋮ Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms ⋮ Every polynomial-time 1-degree collapses if and only if P = PSPACE ⋮ Time and space complexity of reversible pebbling ⋮ Reversible Pebble Game on Trees ⋮ Reversibility in space-bounded computation ⋮ Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ Adaptively secure garbling schemes for parallel computations ⋮ Pebbling meets coloring: reversible pebble game on trees ⋮ Common knowledge and update in finite environments ⋮ Quantum one-way permutation over the finite field of two elements ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Energy efficient sorting, selection and searching ⋮ Fundamentals of reversible flowchart languages ⋮ Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks ⋮ Quantum time/memory/data tradeoff attacks ⋮ Optimizing quantum space using spooky pebble games ⋮ Clean Reversible Simulations of Ranking Binary Trees ⋮ The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs ⋮ Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3 ⋮ New results on \(\mathsf{Gimli}\): full-permutation distinguishers and improved collisions ⋮ Reversible computing from a programming language perspective ⋮ On treewidth, separators and Yao's garbling ⋮ The cost of adaptivity in security games on graphs ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Space-bounded quantum complexity ⋮ Reversibility of computations in graph-walking automata ⋮ Reversible computing and cellular automata -- a survey ⋮ PSPACE-completeness of certain algorithmic problems on the subgroups of free groups ⋮ Inverse monoids associated with the complexity class NP ⋮ Reversible simulation of space-bounded computations ⋮ Low-communication parallel quantum multi-target preimage search ⋮ A class of recursive permutations which is primitive recursive complete ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Quantum circuit oracles for abstract machine computations ⋮ Notes on Landauer's principle, reversible computation, and Maxwell's demon ⋮ A trade-off between classical and quantum circuit size for an attack against CSIDH ⋮ Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Efficient Turing-Universal Computation with DNA Polymers ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Internal symmetries and linear properties: full-permutation distinguishers and improved collisions on \textsf{Gimli} ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ Continuous verifiable delay functions ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ A Hierarchy of Fast Reversible Turing Machines ⋮ Real-Time Methods in Reversible Computation ⋮ Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Reductions and functors from problems to word problems ⋮ Reversible space equals deterministic space ⋮ Quantum search on structured problems ⋮ Boolean satisfiability in quantum compilation ⋮ \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ A common algebraic description for probabilistic and quantum computations ⋮ Quantum computing and quadratically signed weight enumerators ⋮ Quantum neural networks ⋮ ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS ⋮ Breaking the Sub-Exponential Barrier in Obfustopia ⋮ Quantum security analysis of CSIDH
This page was built for publication: Time/Space Trade-Offs for Reversible Computation
