Probabilistic setting of information-based complexity

DOI10.1016/0885-064X(86)90005-1zbMath0627.68040MaRDI QIDQ1092660

Henryk Woźniakowski

Publication date: 1986

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

zbMATH Keywords

approximation; integration; Gaussian measures; probabilistic epsilon-delta complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65D15: Algorithms for approximation of functions

65D30: Numerical integration

Related Items

Average complexity for linear operators over bounded domains, Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure, s-numbers in information-based complexity, On sequential and parallel solution of initial value problems, Orthogonally invariant measures and best approximation of linear operators, Complexity of approximation with relative error criterion in worst, average, and probabilistic settings, An information-based approach to ill-posed problems, The algorithm designer versus nature: A game-theoretic approach to information-based complexity, Complexity of fixed points. I, Measures of uncertainty and information in computation, Information complexity of equations of the second kind with compact operators in Hilbert space, On the adaptive and continuous information problems, Linear widths of a multivariate function space equipped with a Gaussian measure, Information of varying cardinality, Recent developments in information-based complexity

Cites Work

• On the average complexity of multivariate problems
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Gaussian measures in Banach spaces
• Information of varying cardinality
• Some nonlinear problems are as easy as the approximation problem
• Unnamed Item
• Unnamed Item
• Unnamed Item