Liberating the dimension

Abstract: Many recent papers considered the problem of multivariate integration, and studied the tractability of the problem in the worst case setting as the dimensionality increases. The typical question is: can we find an algorithm for which the error is bounded polynomially in , or even independently of ? And the general answer is: yes, if we have a suitably weighted function space. Since there are important problems with infinitely many variables, here we take one step further: we consider the integration problem with infinitely many variables–thus liberating the dimension–and we seek algorithms with small error and minimal cost. In particular, we assume that the cost for evaluating a function depends on the number of active variables. The choice of the cost function plays a crucial role in the infinite dimensional setting. We present a number of lower and upper estimates of the minimal cost for product and finite-order weights. In some cases, the bounds are sharp. [Copyright &y& Elsevier]