Lifting the Curse of Dimensionality: Numerical Integration in Very High Dimensions

Richard Bellman coined the phrase “the curse of dimensionality” to describe the extraordinarily rapid increase in the difficulty of most problems as the number of variables increases. One such problem is numerical multiple integration, where the cost of any integration formula of product type obviously rises exponentially with the number of variables. Nevertheless, problems with hundreds or even thousands of variables do arise, and are now being tackled successfully. In this talk I will tell the story of recent developments, in which within a decade the focus turned from existence theorems to concrete constructions that achieve the theoretically predicted results even for integrals in hundreds or thousands of dimensions many thousands of points. The theory has been shaped by applications, ranging from option pricing to the flow of a liquid through a porous medium, the latter modelled by a partial differential equation with a random permeability field.