Average case optimality for linear problems

DOI10.1016/0304-3975(84)90065-3MaRDI QIDQ796299zbMATH OpenOpenAlexFDO

Authors J. F. Traub, Grzegorz W. Wasilkowski, H. Woźniakowski

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(84)90065-3

zbMATH Keywords

optimal algorithmadaptive informationoptimal informationaverage case modelnon-adaptive information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Recommendations

• Average case optimality
• Average case optimal algorithms in Hilbert spaces
• Average case complexity of linear multivariate problems
• On linear versus nonlinear approximation in the average case setting
• Complexity of multilinear problems in the average case setting
• Tractability of linear multivariate problems in the average case setting
• Average-case non-approximability of optimisation problems
• Fundamentals of Computation Theory
• Average case complexity of linear multivariate problems. II: Applications
• Average case complexity of linear multivariate problems. I: Theory

Cites work

• scientific article; zbMATH DE number 3664338 (Why is no real title available?)
• scientific article; zbMATH DE number 3705887 (Why is no real title available?)
• scientific article; zbMATH DE number 3707731 (Why is no real title available?)
• scientific article; zbMATH DE number 3744505 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3467029 (Why is no real title available?)
• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 3550662 (Why is no real title available?)
• scientific article; zbMATH DE number 3795350 (Why is no real title available?)
• scientific article; zbMATH DE number 3430635 (Why is no real title available?)
• scientific article; zbMATH DE number 3248792 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A New Incompleteness Result for Hoare's System
• An axiomatic basis for computer programming
• Consistent and complementary formal theories of the semantics of programming languages
• Correctness of the compiling process based on axiomatic semantics
• Expressiveness and the completeness of Hoare's logic
• Floyd's principle, correctness theories and program equivalence
• Hoare's logic and Peano's arithmetic
• How to Program an Infinite Abacus
• Programming Language Constructs for Which It Is Impossible To Obtain Good Hoare Axiom Systems
• Soundness and Completeness of an Axiom System for Program Verification
• Two theorems about the completeness of Hoare's logic

Cited in

(32)

• scientific article; zbMATH DE number 4112013 (Why is no real title available?)
• Average case optimality
• Parallel and sequential computation: A statistician's view
• Can adaption help on the average?
• The average a posteriori error of numerical methods
• How powerful is continuous nonlinear information for linear problems?
• A survey of information-based complexity
• Complexity of multilinear problems in the worst case setting
• Orthogonally invariant measures and best approximation of linear operators
• Orthogonal projections are optimal algorithms
• Are linear algorithms always good for linear problems?
• A survey of average case complexity for linear multivariate problems
• Average-case analysis of numerical problems
• Average case optimal algorithms in Hilbert spaces
• Optimal average case estimation in Hilbert norms
• On average case complexity of linear problems with noisy information
• scientific article; zbMATH DE number 139625 (Why is no real title available?)
• scientific article; zbMATH DE number 177344 (Why is no real title available?)
• Optimal algorithms for computing average temperatures
• Solving and learning nonlinear PDEs with Gaussian processes
• Average complexity of divide-and-conquer algorithms
• The verification of modules
• A probabilistic theory for error estimation in automatic integration
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• A stochastic analog to Chebyshev centers and optimal average case algorithms
• A note on varying cardinality in the average case setting
• Optimal linear randomized methods for linear operators in Hilbert spaces
• s-numbers in information-based complexity
• Information of varying cardinality
• Average case complexity of linear multivariate problems
• On average case errors in numerical analysis
• Recent developments in information-based complexity

This page was built for publication: Average case optimality for linear problems

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