Time-space tradeoffs for computing functions, using connectivity properties of their circuits
From MaRDI portal
Publication:5402558
DOI10.1145/800133.804348zbMath1282.68145MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
94C05: Analytic circuit theory
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Lower bounds in algebraic computational complexity, Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer, A space bound for one-tape multidimensional Turing machines, A time-space tradeoff for sorting on non-oblivious machines, Additive complexity in directed computations, A note on time-space tradeoffs for computing continuous functions, Space-time tradeoffs for linear recursion