Average case complexity of multivariate integration for smooth functions (Q1260659)

The computational complexity of multivariate integration is determined as the average case setting, in which cost and error of the approximating multivariate integrals are defined as the expected cost and error with respect to the folded Wiener sheet measure on the class of smooth functions. This average case complexity is derived by using a relation between the average and worst case settings. The main result of the paper is the evaluation of the average case complexity of an optimal algorithm for multivariate integration, where the computation of the optimal sample points, as well as their number, requires preprocessing which increases the computation cost. Also, a different set of fully constructive almost optimal points (that can be preprocessed by using the Monte Carlo algorithm) and an almost optimal algorithm are given with a reduced average case complexity.