Demo Data from EDBT 2026 / reviewers in the wild / expert
Robert Y. Levin
dblp:57/327
· DBLP profile ↗
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › computational models
reversible computation |
0.0 | 1 | 1990 | A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990 |
Computational complexity › computational models
reversible simulation |
0.0 | 1 | 1990 | A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990 |
Computational complexity
time-space tradeoffs |
0.0 | 1 | 1990 | A Note on Bennett's Time-Space Tradeoff for Reversible Computation · SIAM J. Comput. 1990 |
Computational complexity › computational models
simulation complexity |
0.0 | 1 | 1990 | 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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 1990 | A Note on Bennett's Time-Space Tradeoff for Reversible ComputationabstractGiven 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 |