Probabilistic setting of information-based complexity

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

Henryk 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

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

Related Items (19)

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 ⋮ Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games ⋮ Recent developments in information-based complexity ⋮ On sequential and parallel solution of initial value problems ⋮ Orthogonally invariant measures and best approximation of linear operators ⋮ Measures of uncertainty and information in computation ⋮ Information complexity of equations of the second kind with compact operators in Hilbert space ⋮ Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients ⋮ Linear widths of a multivariate function space equipped with a Gaussian measure ⋮ Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure ⋮ Average complexity for linear operators over bounded domains ⋮ De-noising by thresholding operator adapted wavelets ⋮ On the adaptive and continuous information problems ⋮ s-numbers in information-based complexity ⋮ Information of varying cardinality ⋮ Hyperbolic cross and the complexity of various classes of ill-posed linear problems

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

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