Average case optimality for linear problems

DOI10.1016/0304-3975(84)90065-3zbMath0543.68029OpenAlexW2150726636MaRDI QIDQ796299

J. F. Traub, Henryk Woźniakowski, Grzegorz W. Wasilkowski

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 algorithmoptimal informationadaptive informationaverage case modelnon-adaptive information

Mathematics Subject Classification ID

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

Related Items (20)

The verification of modules ⋮ A survey of information-based complexity ⋮ Parallel and sequential computation: A statistician's view ⋮ Solving and learning nonlinear PDEs with Gaussian processes ⋮ Average complexity of divide-and-conquer algorithms ⋮ A probabilistic theory for error estimation in automatic integration ⋮ Recent developments in information-based complexity ⋮ Orthogonally invariant measures and best approximation of linear operators ⋮ Tractability of infinite-dimensional integration in the worst case and randomized settings ⋮ A survey of average case complexity for linear multivariate problems ⋮ Optimal linear randomized methods for linear operators in Hilbert spaces ⋮ s-numbers in information-based complexity ⋮ Can adaption help on the average? ⋮ Information of varying cardinality ⋮ On average case errors in numerical analysis ⋮ How powerful is continuous nonlinear information for linear problems? ⋮ Orthogonal projections are optimal algorithms ⋮ The average a posteriori error of numerical methods ⋮ Average case optimality ⋮ Average case optimal algorithms in Hilbert spaces

Cites Work

• Two theorems about the completeness of Hoare's logic
• Expressiveness and the completeness of Hoare's logic
• Correctness of the compiling process based on axiomatic semantics
• Floyd's principle, correctness theories and program equivalence
• Hoare's logic and Peano's arithmetic
• Consistent and complementary formal theories of the semantics of programming languages
• How to Program an Infinite Abacus
• A New Incompleteness Result for Hoare's System
• Soundness and Completeness of an Axiom System for Program Verification
• Programming Language Constructs for Which It Is Impossible To Obtain Good Hoare Axiom Systems
• An axiomatic basis for computer programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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