Liberating the Dimension for Function Approximation and Integration

G. W. Wasilkowski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations


We discuss recent results on the complexity and tractability of problems dealing with ∞-variate functions. Such problems, especially path integrals, arise in many areas including mathematical finance, quantum physics and chemistry, and stochastic differential equations. It is possible to replace the ∞-variate problem by one that has only d variables since the difference between the two problems diminishes with d approaching infinity. Therefore, one could use algorithms obtained in the Information-Based Complexity study, where problems with arbitrarily large but fixed d have been analyzed. However, to get the optimal results, the choice of a specific value of d should be a part of an efficient algorithm. This is why the approach discussed in the present paper is called liberating the dimension. Such a choice should depend on the cost of sampling d-variate functions and on the error demand ∈. Actually, as recently observed for a specific class of problems, optimal algorithms are from a family of changing dimension algorithms which approximate ∞-variate functions by a combination of special functions, each depending on a different set of variables. Moreover, each such set contains no more than d(∈) = O(ln(1/∈)/ln(ln(1/∈))) variables. This is why the new algorithms have the total cost polynomial in 1/∈ even if the cost of sampling a d-variate function is exponential in d.

Original languageEnglish
Title of host publicationMonte Carlo and Quasi-Monte Carlo Methods 2010
Number of pages21
StatePublished - 2012
Event9th International Conference on Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, MCQMC 2010 - Warsaw, Poland
Duration: Aug 15 2010Aug 20 2010

Publication series

NameSpringer Proceedings in Mathematics and Statistics
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017


Conference9th International Conference on Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, MCQMC 2010

ASJC Scopus subject areas

  • Mathematics (all)


Dive into the research topics of 'Liberating the Dimension for Function Approximation and Integration'. Together they form a unique fingerprint.

Cite this