The algorithm designer versus nature: A game-theoretic approach to information-based complexity

DOI10.1016/0885-064X(87)90014-8zbMath0641.68062MaRDI QIDQ1100895

Edward W. Packel

Publication date: 1987

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

zbMATH Keywords

information-based complexityaverage case analysistwo-person zero-sum gamerandomized setting

Mathematics Subject Classification ID

2-person games (91A05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Measures of information, entropy (94A17)

Related Items (4)

Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games ⋮ Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients ⋮ A minimax principle for the optimal error of Monte Carlo methods ⋮ Quadrature Formulas for Monotone Functions

Cites Work

• Average case optimality
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Probabilistic setting of information-based complexity
• Randomization for continuous problems
• Information of varying cardinality
• Do Linear Problems Have Linear Optimal Algorithms?
• Recent developments in information-based complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The algorithm designer versus nature: A game-theoretic approach to information-based complexity