Lower bounds for the complexity of linear functionals in the randomized setting

DOI10.1016/J.JCO.2010.08.002MaRDI QIDQ617652zbMATH OpenOpenAlexFDO

Authors Erich Novak, H. Woźniakowski

Publication date 21 January 2011

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

Full work available at URL https://doi.org/10.1016/j.jco.2010.08.002

zbMATH Keywords

complexity in the randomized settingsdecomposable kernelsintegration over reproducing kernel Hilbert spacesoptimal Monte Carlo method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22)

Recommendations

• The power of standard information for multivariate approximation in the randomized setting
• On the power of standard information for \(L_{\infty}\) approximation in the randomized setting
• scientific article; zbMATH DE number 2161076
• Tractability of tensor product linear operators
• scientific article; zbMATH DE number 5286769

Cites work

• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• Deterministic and stochastic error bounds in numerical analysis
• Intractability results for integration and discrepancy
• Optimal importance sampling for the approximation of integrals
• The power of standard information for multivariate approximation in the randomized setting
• Theory of Reproducing Kernels
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Variational properties of averaged equations for periodic media

Cited in

(7)

• Probabilistic complexity analysis for linear problems in bounded domains
• Lower space bounds for randomized computation
• Linear FPT reductions and computational lower bounds
• scientific article; zbMATH DE number 1534573 (Why is no real title available?)
• Lower bound on complexity of optimization of continuous functions
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• Some results on the complexity of numerical integration

This page was built for publication: Lower bounds for the complexity of linear functionals in the randomized setting

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