Liberating the dimension

Many recent papers considered the problem of multivariate integration, and studied the tractability   of the problem in the worst case setting as the dimensionality dd increases. The typical question is: can we find an algorithm for which the error is bounded polynomially in dd, or even independently of dd? 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.