Time-space tradeoffs for computing functions, using connectivity properties of their circuits

DOI10.1145/800133.804348zbMath1282.68145OpenAlexW2126370441MaRDI QIDQ5402558

Martin Tompa

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

Mathematics Subject Classification ID

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