Time-space tradeoffs for computing functions, using connectivity properties of their circuits
From MaRDI portal
Publication:5402558
DOI10.1145/800133.804348zbMath1282.68145OpenAlexW2126370441MaRDI QIDQ5402558
Publication date: 14 March 2014
Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/800133.804348
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analytic circuit theory (94C05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (11)
Space-time tradeoffs for linear recursion ⋮ Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks ⋮ A space bound for one-tape multidimensional Turing machines ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Additive complexity in directed computations ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ A note on time-space tradeoffs for computing continuous functions ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Lower bounds in algebraic computational complexity ⋮ Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer ⋮ Depth-Robust Graphs and Their Cumulative Memory Complexity
This page was built for publication: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
