Curse of dimensionality

Summary

The curse of dimensionality is the exponential growth in the dimension $d$ of the cost of solving a numerical problem to a fixed accuracy. The phrase is due to Richard Bellman. In integration and approximation it means that the number of function values needed for error $\varepsilon$ grows like $c^d$ with $c > 1$. Methods such as sparse grids, Monte Carlo and quasi-Monte Carlo methods, and restrictions to special classes of functions are ways to avoid it.