Probabilistic setting of information-based complexity

DOI10.1016/0885-064X(86)90005-1MaRDI QIDQ1092660zbMATH OpenOpenAlexFDO

Authors H. Woźniakowski

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0885-064x(86)90005-1

zbMATH Keywords

approximationintegrationGaussian measuresprobabilistic epsilon-delta complexity

Mathematics Subject Classification ID

Numerical integration (65D30) Analysis of algorithms and problem complexity (68Q25) Algorithms for approximation of functions (65D15)

Recommendations

• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Probabilistic complexity analysis for linear problems in bounded domains
• On average case complexity of linear problems with noisy information
• scientific article; zbMATH DE number 953052
• Optimal algorithms for linear problems with Gaussian measures

Cites work

• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• scientific article; zbMATH DE number 3456359 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Gaussian measures in Banach spaces
• Information of varying cardinality
• On the average complexity of multivariate problems
• Some nonlinear problems are as easy as the approximation problem

Cited in

(23)

• On sequential and parallel solution of initial value problems
• Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients
• Estimating information amount under uncertainty: algorithmic solvability and computational complexity
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• The algorithm designer versus nature: A game-theoretic approach to information-based complexity
• On the adaptive and continuous information problems
• Recent developments in information-based complexity
• Average complexity for linear operators over bounded domains
• Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games
• Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure
• s-numbers in information-based complexity
• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Information complexity of equations of the second kind with compact operators in Hilbert space
• Orthogonally invariant measures and best approximation of linear operators
• Linear widths of a multivariate function space equipped with a Gaussian measure
• Complexity of fixed points. I
• Information of varying cardinality
• Measures of uncertainty and information in computation
• Complexity of verification and computation for IBC problems
• De-noising by thresholding operator adapted wavelets
• An information-based approach to ill-posed problems
• Information-theoretic lower bound on energy cost of stochastic computation
• Hyperbolic cross and the complexity of various classes of ill-posed linear problems

This page was built for publication: Probabilistic setting of information-based complexity

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