Time/Space Trade-Offs for Reversible Computation

Cited In (83)

Boolean satisfiability in quantum compilation
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
Title not available (Why is that?)
Efficient and exact quantum compression
An introduction to quantum computing for statisticians and data scientists
Towards clean reversible lossless compression. A reversible programming experiment with zip
Energy efficient sorting, selection and searching
Improving generic attacks using exceptional functions
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
Reversible Pebble Game on Trees
Real-Time Methods in Reversible Computation
Energy efficient sorting, selection and searching
The cost of adaptivity in security games on graphs
Quantum circuits for high-degree and half-multiplication for post-quantum analysis
Reversibility of computations in graph-walking automata
Quantum computing and quadratically signed weight enumerators
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
Reversible and Irreversible Computations of Deterministic Finite-State Devices
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
Periodicity and Immortality in Reversible Computing
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
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
Simpler constructions of asymmetric primitives from obfuscation
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
Improved Quantum Circuits for Elliptic Curve Discrete Logarithms
Improved reversible and quantum circuits for Karatsuba-based integer multiplication.
The word problem of the Brin-Thompson group is \textsf{coNP}-complete
LESS is More: Code-Based Signatures Without Syndromes
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
The complexity of reversible cellular automata
Common knowledge and update in finite environments
Internal symmetries and linear properties: full-permutation distinguishers and improved collisions on \textsf{Gimli}
Pebbling meets coloring: reversible pebble game on trees
Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks
Efficient Turing-Universal Computation with DNA Polymers
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
Quantum one-way permutation over the finite field of two elements
Quantum neural networks
ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS
New results on \(\mathsf{Gimli}\): full-permutation distinguishers and improved collisions
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
A Hierarchy of Fast Reversible Turing Machines
Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics
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
Breaking the Sub-Exponential Barrier in Obfustopia
Adaptively secure garbling schemes for parallel computations

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)