Average case optimality for linear problems

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

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

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 algorithm; optimal information; adaptive information; average case model; non-adaptive information

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W99: Algorithms in computer science

Related Items

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

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