Time/Space Trade-Offs for Reversible Computation
From MaRDI portal
Publication:3832041
DOI10.1137/0218053zbMATH Open0676.68010OpenAlexW2061073612MaRDI QIDQ3832041FDOQ3832041
Authors: Charles H. Bennett 
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/500470befb771a5cb10095103f50b4cda75ff008
Recommendations
Cited In (92)
- Quantum computing and quadratically signed weight enumerators
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Ricercar: a language for describing and rewriting reversible circuits with ancillae and its permutation semantics
- Title not available (Why is that?)
- Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
- Quantum circuit oracles for abstract machine computations
- Low-gate quantum golden collision finding
- A class of recursive permutations which is primitive recursive complete
- Algorithmic arguments in physics of computation
- Notes on Landauer's principle, reversible computation, and Maxwell's demon
- The stochastic thermodynamics of computation
- Reversible parallel computation: An evolving space-model
- Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
- Reversible computing and cellular automata -- a survey
- Reversibility and adiabatic computation: trading time and space for energy
- Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
- Computability and complexity of ray tracing
- Low-communication parallel quantum multi-target preimage search
- Quantum security analysis of CSIDH
- Reversible computing from a programming language perspective
- Breaking the sub-exponential barrier in obfustopia
- Periodicity and Immortality in Reversible Computing
- Efficient Turing-universal computation with DNA polymers
- An unambiguous class possessing a complete set
- A common algebraic description for probabilistic and quantum computations
- PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
- A trade-off between classical and quantum circuit size for an attack against CSIDH
- Quantum Chebyshev's Inequality and Applications
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- On treewidth, separators and Yao's garbling
- Time and space bounds for reversible simulation
- Reversible pebble games and the relation between tree-like and general resolution space
- Nullstellensatz size-degree trade-offs from reversible pebbling
- Continuous verifiable delay functions
- Quantitative Analysis of Concurrent Reversible Computations
- Space-bounded quantum complexity
- Fundamentals of reversible flowchart languages
- \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
- Nullstellensatz size-degree trade-offs from reversible pebbling
- The word problem of the Brin-Thompson group is \textsf{coNP}-complete
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- The complexity of reversible cellular automata
- Common knowledge and update in finite environments
- Pebbling meets coloring: reversible pebble game on trees
- When-and how-can a cellular automaton be rewritten as a lattice gas?
- One-way permutations, computational asymmetry and distortion.
- Every polynomial-time 1-degree collapses if and only if P = PSPACE
- Time complexity of tape reduction for reversible Turing machines
- Quantum one-way permutation over the finite field of two elements
- A hierarchy of fast reversible Turing machines
- Programming techniques for reversible comparison sorts
- Quantum neural networks
- ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS
- Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
- Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
- Reductions and functors from problems to word problems
- Reversible space equals deterministic space
- Reversibility in space-bounded computation
- Quantum search on structured problems
- Inverse monoids associated with the complexity class NP
- LESS is more: code-based signatures without syndromes
- Reversible and irreversible computations of deterministic finite-state devices
- Static-memory-hard functions, and modeling the cost of space vs. time
- Reversible simulation of space-bounded computations
- Time and space complexity of reversible pebbling
- A tradeoff theorem for space and reversal
- Adaptively secure garbling schemes for parallel computations
- Improved reversible and quantum circuits for Karatsuba-based integer multiplication
- Reversibility of computations in graph-walking automata
- Boolean satisfiability in quantum compilation
- Quantum time/memory/data tradeoff attacks
- Optimizing quantum space using spooky pebble games
- The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
- Balloon hashing: a memory-hard function providing provable protection against sequential attacks
- Title not available (Why is that?)
- Toward an energy efficient language and compiler for (partially) reversible algorithms
- Efficient and exact quantum compression
- Simpler constructions of asymmetric primitives from obfuscation
- An introduction to quantum computing for statisticians and data scientists
- Reversible pebble game on trees
- Internal symmetries and linear properties: full-permutation distinguishers and improved collisions on \textsf{Gimli}
- Real-time methods in reversible computation
- Towards clean reversible lossless compression. A reversible programming experiment with zip
- Energy efficient sorting, selection and searching
- Clean reversible simulations of ranking binary trees
- Improving generic attacks using exceptional functions
- New results on \(\mathsf{Gimli}\): full-permutation distinguishers and improved collisions
- Energy efficient sorting, selection and searching
- The cost of adaptivity in security games on graphs
- Improved quantum circuits for elliptic curve discrete logarithms
- Quantum circuits for high-degree and half-multiplication for post-quantum analysis
This page was built for publication: Time/Space Trade-Offs for Reversible Computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3832041)
