Complexity of linear problems with a fixed output basis

DOI10.1006/JCOM.1999.0538MaRDI QIDQ1977152zbMATH OpenOpenAlexFDO

Authors Erich Novak, H. Woźniakowski

Publication date 9 May 2000

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

Full work available at URL https://doi.org/10.1006/jcom.1999.0538

zbMATH Keywords

information-based complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Linear vs. nonlinear algorithms for linear problems
• Do Linear Problems Have Linear Optimal Algorithms?
• Recent developments in information-based complexity
• scientific article; zbMATH DE number 822135
• scientific article; zbMATH DE number 139625

Cites work

• Are linear algorithms always good for linear problems?
• scientific article; zbMATH DE number 3938445 (Why is no real title available?)
• 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 1215245 (Why is no real title available?)
• scientific article; zbMATH DE number 1246413 (Why is no real title available?)
• scientific article; zbMATH DE number 1069611 (Why is no real title available?)
• scientific article; zbMATH DE number 953047 (Why is no real title available?)
• scientific article; zbMATH DE number 919117 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the cost of uniform and nonuniform algorithms
• On the optimality of linear methods for operator approximation in convex classes of functions
• On the power of adaption
• On the topology of algorithms. I
• Optimal sequential and non-sequential procedures for evaluating a functional
• s-numbers in information-based complexity
• The real number model in numerical analysis
• Topological complexity of zero-finding
• Topological complexity with continuous operations
• Why does information-based complexity use the real number model?

Cited in

(6)

• On low-complexity approximation of matrices
• Optimal approximation of elliptic problems by linear and nonlinear mappings. I
• Optimal approximation of elliptic problems by linear and nonlinear mappings. II
• A decision procedure for linear ``big O equations
• Some basic information on information-based complexity theory
• Linear vs. nonlinear algorithms for linear problems

This page was built for publication: Complexity of linear problems with a fixed output basis

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