A note on time-space tradeoffs for computing continuous functions

DOI10.1016/0020-0190(79)90027-9zbMath0412.68039OpenAlexW2066161457WikidataQ97309503 ScholiaQ97309503MaRDI QIDQ1259903

Harold Abelson

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90027-9

zbMATH Keywords

computational complexitysortingsums of powerstime-space tradeoffsroots of a polynomialcomputing continuous functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Real polynomials: location of zeros (26C10) Continuity and differentiation questions (26B05)

Related Items

Recursive construction for 3-regular expanders ⋮ Eigenvalues and expanders ⋮ Time-space tradeoffs for computing functions, using connectivity properties of their circuits ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Size bounds for superconcentrators ⋮ Highly symmetric expanders ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory

Cites Work

• Graph-theoretic properties in computational complexity
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits