The Curse of Dimensionality for Numerical Integration of Smooth Functions
Establishes a fundamental lower bound for numerical integration of smooth functions, showing that high-dimensional integration is inherently hard regardless of smoothness.
The paper proves that multivariate integration of C^r smooth functions suffers from the curse of dimensionality, requiring at least c_r (1+γ)^d function evaluations to achieve error ε, where d is the dimension.
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.