The Complexity of Multivariate Integration

Multivariate integration is one of the prime examples for complexity studies of high dimensional problems. In this talk we review what is known for deterministic and randomized algorithms, present some new approaches and look at related open problems. We discuss negative results in the deterministic setting such as the curse of dimensionality even for some small classes of smooth functions. We also discuss in some detail positive results on the power of randomized algorithms, in particular importance sampling. An abstract but nonconstructive approach gives a rather general tractability theorem for integration of functions from reproducing kernel Hilbert spaces. We exhibit cases for which the sampling density for the algorithm can be given explicitly based on certain Sobolev type inequalities.