1989 Reports

Average Case Complexity of Multivariate Integration

Wozniakowski, Henryk

We study the average case complexity of multivariate integration for the class of continuous functions of d variables equipped with the classical Wiener sheet measure. To derive the average case complexity one needs to obtain optimal sample points. We prove that optimal design is closely related to discrepancy theory which has been extensively studied for many years. This relation enables us to show that optimal sample points can be derived from Hammersley points. Extending the result of Roth and using the recent result of Wasilkowski, we conclude that the average case complexity is θ(ε-1(lnε-1)(d-1)/2)