On Time Versus Space - MaRDI portal

Cited In (62)

On probabilistic space-bounded machines with multiple access to random tape
Rounds versus time for the two person pebble game
Sustained space and cumulative complexity trade-offs for data-dependent memory-hard functions
Herscovici's conjecture on products of shadow graphs of paths
Tighter connections between Formula-SAT and shaving logs
On time versus space. II
Expanders, randomness, or time versus space
A comparison of two variations of a pebble game on graphs
On 3-pushdown graphs with large separators
Min Cut is NP-complete for edge weighted trees
A partial k-arboretum of graphs with bounded treewidth
Relativized alternation and space-bounded computation
Cumulative space in black-white pebbling and resolution
Observations on the complexity of regular expression problems
Number of quantifiers is better than number of tape cells
Towards separating nondeterminism from determinism
Balloon hashing: a memory-hard function providing provable protection against sequential attacks
Searching and pebbling
Bandwidth and pebbling
A note on the pebble game
A space bound for one-tape multidimensional Turing machines
Nullstellensatz size-degree trade-offs from reversible pebbling
Time-space trade-offs in a pebble game
Parallel computation with threshold functions
Nullstellensatz size-degree trade-offs from reversible pebbling
Time complexity of multidimensional Turing machines
Extreme time-space tradeoffs for graphs with small space requirements
Data structures for distributed counting
Improved simulation of nondeterministic Turing machines
On time hierarchies
Sorting, linear time and the satisfiability problem
The size and depth of layered Boolean circuits
Amplifying circuit lower bounds against polynomial time, with applications
On relationships between complexity classes of Turing machines
Pebble games for studying storage sharing
Alternating time versus deterministic time: A separation
On Reducing the Space Requirements of a Straight-Line Algorithm
Classifying the computational complexity of problems
Complexity lower bounds for machine computing models
Space-bounded simulation of multitape turing machines
Time-space tradeoffs for SAT on nonuniform machines
Speedups of deterministic machines by synchronous parallel machines
On time versus space III
On alternation
The complexity of matrix transposition on one-tape off-line Turing machines
Space-time tradeoffs for linear recursion
On the cost of recomputing: Tight bounds on pebbling with faults
On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
On the relationship between deterministic time and deterministic reversal
Proofs of space
A view of computability on term algebras
On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines
The space complexity of pebble games on trees
Parallelizing time with polynomial circuits
Static-memory-hard functions, and modeling the cost of space vs. time
Synchronizing automata over nested words
Complexity of nondeterministic multitape computations based on crossing sequences
On the cost of recomputing: tight bounds on pebbling with faults
The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
Rounds versus time for the two person pebble game (extended abstract)
On the target pebbling conjecture
Nonuniform complexity classes specified by lower and upper bounds

This page was built for publication: On Time Versus Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4131020)