The Curse of Dimensionality for Numerical Integration of Smooth Functions

Abstract

We prove the curse of dimensionality for multivariate integration of C^r functions: The number of needed function values to achieve an error ε is larger than c_r (1+γ)^d for ε\le ε_0, where c_r,γ>0 and d is the dimension. The proofs are based on volume estimates for r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r>1.

15 pages, minor revision

References in corpus (1)

• The Curse of Dimensionality for Monotone and Convex Functions of Many Variables

Cited by in corpus (9)

• The Fermion Sign Problem in Path Integral Monte Carlo Simulations: Quantum Dots, Ultracold Atoms, and Warm Dense Matter
• Few-body Bose gases in low dimensions -- a laboratory for quantum dynamics
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• The curse of dimensionality for numerical integration on general domains
• On Weak Tractability of the Clenshaw-Curtis Smolyak Algorithm
• Exponential tractability of $L_2$-approximation with function values
• Product rules are optimal for numerical integration in classical smoothness spaces
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• Approximation of Functions: Optimal Sampling and Complexity