Linearity of algorithms and a result of Ando

DOI10.1016/0885-064X(91)90007-KMaRDI QIDQ1179033zbMATH OpenOpenAlexFDO

Authors Mark Kon, Roberto Tempo

Publication date 26 June 1992

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(91)90007-k

zbMATH Keywords

information-based complexityalmost strongly optimal algorithms on \(L^ p\) spaces

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Normed linear spaces and Banach spaces; Banach lattices (46B99)

Recommendations

• Linear algorithms with finite deviation
• scientific article; zbMATH DE number 139625
• On the complexity of linearizability
• Aspects of Linear Complexity
• Algorithms for computing the linearity and degree of vectorial Boolean functions
• Linear problems and linear algorithms
• scientific article; zbMATH DE number 3936517
• Linear complexity and related complexity measures
• scientific article; zbMATH DE number 4141416

Cites work

• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3455838 (Why is no real title available?)
• scientific article; zbMATH DE number 3314644 (Why is no real title available?)
• Are linear algorithms always good for linear problems?
• Contractive projections in \(L_ p\)-spaces
• Do Linear Problems Have Linear Optimal Algorithms?
• Linear problems (with extended range) have linear optimal algorithms
• On linearity of spline algorithms
• Recent developments in information-based complexity

Cited in

(9)

• Linear algorithms with finite deviation
• Worst-case analysis of the least-squares method and related identification methods
• Optimal numerical approximation of a linear operator
• Homogeneous algorithms and solvable problems on cones
• Linear problems (with extended range) have linear optimal algorithms
• scientific article; zbMATH DE number 177344 (Why is no real title available?)
• Approximation of linear functionals on a Banach space with a Gaussian measure
• scientific article; zbMATH DE number 2007678 (Why is no real title available?)
• On linearity of spline algorithms

This page was built for publication: Linearity of algorithms and a result of Ando

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