The Curse of Dimensionality for Numerical Integration of Smooth Functions

Aicke Hinrichs, Erich Novak, Mario Ullrich, Henryk Wozniakowski

Published 2012-11-05, updated 2013-04-16Version 2

We prove the curse of dimensionality for multivariate integration of C^r functions: The number of needed function values to achieve an error \epsilon\ is larger than c_r (1+\gamma)^d for \epsilon\le \epsilon_0, where c_r,\gamma>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.