A note on time-space tradeoffs for computing continuous functions

DOI10.1016/0020-0190(79)90027-9MaRDI QIDQ1259903zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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) Continuity and differentiation questions (26B05) Real polynomials: location of zeros (26C10)

Cites work

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

Cited in

(7)

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

This page was built for publication: A note on time-space tradeoffs for computing continuous functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1259903)