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

DOI10.1016/J.JCO.2010.08.002zbMATH Open1210.65005OpenAlexW1974657772MaRDI QIDQ617652FDOQ617652

H. Woźniakowski, Erich Novak

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)

Cites Work

• Theory of Reproducing Kernels
• Title not available (Why is that?)
• Deterministic and stochastic error bounds in numerical analysis
• The power of standard information for multivariate approximation in the randomized setting
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Intractability results for integration and discrepancy
• Variational properties of averaged equations for periodic media
• Optimal importance sampling for the approximation of integrals

Cited In (7)

• Some Results on the Complexity of Numerical Integration
• Probabilistic complexity analysis for linear problems in bounded domains
• Lower space bounds for randomized computation
• Linear FPT reductions and computational lower bounds
• Title not available (Why is that?)
• Lower bound on complexity of optimization of continuous functions
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Tractability of tensor product linear operators 👍 👎
• Title not available (Why is that?) 👍 👎

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)