On Time Versus Space - MaRDI portal

Cited in

(62)

Synchronizing automata over nested words
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
Complexity of nondeterministic multitape computations based on crossing sequences
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
On the cost of recomputing: tight bounds on pebbling with faults
A partial k-arboretum of graphs with bounded treewidth
Relativized alternation and space-bounded computation
Observations on the complexity of regular expression problems
Number of quantifiers is better than number of tape cells
Cumulative space in black-white pebbling and resolution
Towards separating nondeterminism from determinism
The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs
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
Time-space trade-offs in a pebble game
Nullstellensatz size-degree trade-offs from reversible pebbling
Rounds versus time for the two person pebble game (extended abstract)
On the target pebbling conjecture
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
Complexity lower bounds for machine computing models
Classifying the computational complexity of problems
Space-bounded simulation of multitape turing machines
Speedups of deterministic machines by synchronous parallel machines
Time-space tradeoffs for SAT on nonuniform machines
On time versus space III
On alternation
Nonuniform complexity classes specified by lower and upper bounds
The complexity of matrix transposition on one-tape off-line Turing machines
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}\)
Space-time tradeoffs for linear recursion
On the relationship between deterministic time and deterministic reversal
A view of computability on term algebras
Proofs of space
On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
The space complexity of pebble games on trees
Static-memory-hard functions, and modeling the cost of space vs. time
Parallelizing time with polynomial circuits

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)