Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Robert Y. Levin

dblp:57/327 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
0since 2021 · last 1990
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › computational models
reversible computation
0.011990
A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990
Computational complexity › computational models
reversible simulation
0.011990
A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990
Computational complexity
time-space tradeoffs
0.011990
A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990
Computational complexity › computational models
simulation complexity
0.011990
A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990

Methods — techniques the papers use, named apart from their topics

recurrence equations · 0.0asymptotic analysis · 0.0
YearPublicationVenuePosition
1990 A Note on Bennett's Time-Space Tradeoff for Reversible Computation
abstract
Given any irreversible program with running time T and space complexity S, and given any $\varepsilon > 0$, Bennett shows how to construct an equivalent reversible program with running time $O(T^{1+\varepsilon })$ and space complexity $O(S \ln T)$. Although these loose upper bounds are formally correct, they are misleading due to a hidden constant factor in the space bound. It is shown that this constant factor is approximately $\varepsilon 2^{1 / \varepsilon}$, which diverges exponentially as $\varepsilon$ approaches 0. Bennett’s analysis is simplified using recurrence equations and it is proven that the reversible program actually runs in time $\Theta ({{T^{1 + \varepsilon}} / {S^{\varepsilon}}})$ and space $\Theta (S(1+\ln ({T / S})))$. Bennett claims that for any $\varepsilon > 0$, the reversible program can be made to run in time $O(T)$ and space $O(ST^{\varepsilon })$. This claim is corrected and tightened as follows: whenever $T \geqq 2S$ and for any $\varepsilon \geqq {1 / {(0.58 \lg ({T / S}))}}$, the reversible program can be made to run in time $\Theta (T)$ and space $\Omega (S(T/S)^{\varepsilon/2})\cap O(S(T/S)^\varepsilon )$. For $S\leqq T < 2S$, Bennett’s 1973 simulation yields an equivalent reversible program that runs in time $\Theta (T)$ and space $\Theta (S)$.
Robert Y. Levin, Alan T. Sherman
SIAM J. Comput.1