The following pages link to On Time Versus Space (Q4131020):
Displaying 50 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Improved simulation of nondeterministic Turing machines (Q764330) (← links)
- Data structures for distributed counting (Q794431) (← links)
- The complexity of matrix transposition on one-tape off-line Turing machines (Q808247) (← links)
- A view of computability on term algebras (Q1051428) (← links)
- Complexity lower bounds for machine computing models (Q1057651) (← links)
- Speedups of deterministic machines by synchronous parallel machines (Q1074339) (← links)
- Expanders, randomness, or time versus space (Q1107314) (← links)
- Parallel computation with threshold functions (Q1107324) (← links)
- Min Cut is NP-complete for edge weighted trees (Q1111019) (← links)
- Relativized alternation and space-bounded computation (Q1111024) (← links)
- On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines (Q1122982) (← links)
- On time hierarchies (Q1137384) (← links)
- On alternation (Q1141480) (← links)
- A note on the pebble game (Q1147083) (← links)
- The space complexity of pebble games on trees (Q1147515) (← links)
- Observations on the complexity of regular expression problems (Q1149249) (← links)
- A comparison of two variations of a pebble game on graphs (Q1149448) (← links)
- A space bound for one-tape multidimensional Turing machines (Q1152219) (← links)
- On time versus space. II (Q1152954) (← links)
- Pebble games for studying storage sharing (Q1162159) (← links)
- Number of quantifiers is better than number of tape cells (Q1164622) (← links)
- Time complexity of multidimensional Turing machines (Q1168311) (← links)
- Extreme time-space tradeoffs for graphs with small space requirements (Q1173412) (← links)
- On the relationship between deterministic time and deterministic reversal (Q1209341) (← links)
- Time-space trade-offs in a pebble game (Q1254254) (← links)
- A partial k-arboretum of graphs with bounded treewidth (Q1274912) (← links)
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\) (Q1401330) (← links)
- On the cost of recomputing: Tight bounds on pebbling with faults (Q1575959) (← links)
- Static-memory-hard functions, and modeling the cost of space vs. time (Q1629397) (← links)
- On relationships between complexity classes of Turing machines (Q1682916) (← links)
- Sorting, linear time and the satisfiability problem (Q1817067) (← links)
- Searching and pebbling (Q1821562) (← links)
- Bandwidth and pebbling (Q1838912) (← links)
- The size and depth of layered Boolean circuits (Q1944075) (← links)
- Nullstellensatz size-degree trade-offs from reversible pebbling (Q2040600) (← links)
- On 3-pushdown graphs with large separators (Q2277467) (← links)
- Parallelizing time with polynomial circuits (Q2429726) (← links)
- Rounds versus time for the two person pebble game (Q2641235) (← links)
- Synchronizing Automata over Nested Words (Q2811343) (← links)
- On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape (Q2946415) (← links)
- Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks (Q2958121) (← links)
- On Reducing the Space Requirements of a Straight-Line Algorithm (Q3332245) (← links)
- Towards separating nondeterminism from determinism (Q3334987) (← links)
- Proofs of Space (Q3457086) (← links)
- On time versus space III (Q3745280) (← links)
- Classifying the computational complexity of problems (Q3781088) (← links)
- Space-bounded simulation of multitape turing machines (Q3928247) (← links)
- Space-time tradeoffs for linear recursion (Q3968456) (← links)
- On the cost of recomputing: tight bounds on pebbling with faults (Q4632415) (← links)
