Fetching the paper…
Reading the bibliography…
We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$.
Classes of languages and linear-bounded automata
S.-Y. Kuroda · 1964
Earlier work this paper cites.
Hierarchies of memory limited computations
Richard Edwin Stearns, Juris Hartmanis, and Philip M. Lewis II · 1965
Earlier work this paper cites.
Two-tape simulation of multitape turing machines
F. C. Hennie and Richard Edwin Stearns · 1966
Earlier work this paper cites.
Relations between time and tape complexities
John E. Hopcroft and Jeffrey D. Ullman · 1968
Earlier work this paper cites.
Tape bounds for time-bounded turing machines
Mike Paterson · 1972
Earlier work this paper cites.
Word problems requiring exponential time: Preliminary report
Larry J. Stockmeyer and Albert R. Meyer · 1973
Earlier work this paper cites.
Circuit size is nonlinear in depth
Mike Paterson and Leslie G. Valiant · 1976
Earlier work this paper cites.
On time versus space
John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant · 1977
Earlier work this paper cites.
Fast simulation of combinational logic networks by machines without random-access storage
Nicholas Pippenger · 1977
Earlier work this paper cites.
A probabilistic remark on algebraic program testing
Richard A. DeMillo and Richard J. Lipton · 1978
Earlier work this paper cites.
On Space-Time Tradeoffs
Sowmitri Swamy · 1978
Earlier work this paper cites.
Relations among complexity measures
Nicholas Pippenger and Michael J. Fischer · 1979
Earlier work this paper cites.
On alternation II. A graph theoretic approach to determinism versus nondeterminism
Wolfgang J. Paul and Rüdiger Reischuk · 1980
Earlier work this paper cites.
Space-bounded simulation of multitape turing machines
Leonard M. Adleman and Michael C. Loui · 1981
Earlier work this paper cites.
A space bound for one-tape multidimensional turing machines
Michael C. Loui · 1981
Earlier work this paper cites.
On time versus space II
Wolfgang J. Paul and Rüdiger Reischuk · 1981
Earlier work this paper cites.
Asymptotically tight bounds on time-space trade-offs in a pebble game
Thomas Lengauer and Robert Endre Tarjan · 1982
Earlier work this paper cites.
Some time-space tradeoff results concerning single-tape and offline TM’s
Oscar H. Ibarra and Shlomo Moran · 1983
Earlier work this paper cites.
Optimal dynamic embedding of trees into arrays
Michael C. Loui · 1983
Earlier work this paper cites.
On determinism versus non-determinism and related problems (preliminary version)
Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, and William T. Trotter · 1983
Cited alongside, same era.
Speedups of deterministic machines by synchronous parallel machines
Patrick W. Dymond and Martin Tompa · 1985
Cited alongside, same era.
On time versus space III
Joseph Y. Halpern, Michael C. Loui, Albert R. Meyer, and Daniel Weise · 1986
Cited alongside, same era.
Bounded oracles and complexity classes inside linear space
Carol Tretkoff · 1986
Cited alongside, same era.
Expanders, randomness, or time versus space
Michael Sipser · 1988
Cited alongside, same era.
The problem of space invariance for sequential machines
Cees F. Slot and Peter van Emde Boas · 1988
Cited alongside, same era.
Time-space lower bounds for satisfiability
Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas · 2005
Later among the works it cites.
Simulating undirected st -connectivity algorithms on uniform JAGs and NNJAGs
Pinyan Lu, Jialin Zhang, Chung Keung Poon, and Jin-yi Cai · 2005
Later among the works it cites.
Random access to advice strings and collapsing results
Jin-yi Cai and Osamu Watanabe · 2006
Later among the works it cites.
Computational complexity - a conceptual perspective
Oded Goldreich · 2008
Later among the works it cites.
Undirected connectivity in log-space
Omer Reingold · 2008
Later among the works it cites.
Non-linear time lower bound for (succinct) quantified boolean formulas
Ryan Williams · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fast simulations of time-bounded one-tape turing machines by space-bounded ones
Maciej Liskiewicz and Krzysztof Lorys · 1990
Cited alongside, same era.
Machine models and simulation
Peter van Emde Boas · 1990
Cited alongside, same era.
Lower bounds for deterministic and nondeterministic branching programs
Alexander A. Razborov · 1991
Cited alongside, same era.
Relativization: a revisionistic retrospective
Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, and Pankaj Rohatgi · 1993
Cited alongside, same era.
Space bounds for graph connectivity problems on node-named jags and node-ordered jags
Chung Keung Poon · 1993
Cited alongside, same era.
Hardness vs randomness
Noam Nisan and Avi Wigderson · 1994
Cited alongside, same era.
Computational Complexity - A Modern Approach
Sanjeev Arora and Boaz Barak · 2009
Later among the works it cites.
The complexity of satisfiability of small depth circuits
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi · 2009
Later among the works it cites.
Improved simulation of nondeterministic turing machines
Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, and Farbod Shokrieh · 2011
Later among the works it cites.
Pebbles and branching programs for tree evaluation
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam · 2012
Later among the works it cites.
Boolean Function Complexity - Advances and Frontiers
Stasys Jukna · 2012
Later among the works it cites.
Amplifying circuit lower bounds against polynomial time, with applications
Richard J. Lipton and Ryan Williams · 2013
Later among the works it cites.
Easiness amplification and uniform circuit lower bounds
Cody D. Murray and R. Ryan Williams · 2017
Later among the works it cites.
Catalytic approaches to the tree evaluation problem
James Cook and Ian Mertz · 2020
Later among the works it cites.
Encodings and the tree evaluation problem
James Cook and Ian Mertz · 2021
Later among the works it cites.
Trading time and space in catalytic branching programs
James Cook and Ian Mertz · 2022
Later among the works it cites.
Tree evaluation is in space O(log n ⋅ \cdot log log n)
James Cook and Ian Mertz · 2024
Later among the works it cites.
On the Cook-Mertz Tree Evaluation procedure
Oded Goldreich · 2024
Later among the works it cites.