Tractability of multivariate integration - old and new results and open problems

Multivariate integration is one of the prime examples for complexity studies of high dimensional problems. In this talk we review more or less well-known results for deterministic and randomized algorithms, present some new approaches and look at related open problems. We 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. We also discuss negative results in the deterministic setting such as the curse of dimensionality even for some small classes of smooth functions.