Information-based complexity

Summary

Information-based complexity studies the minimal cost of solving continuous problems, such as integration or approximation of functions, to a given accuracy. An algorithm may learn the input only through finitely many measurements, for example function values, so the information it has is partial. The central quantities are the smallest error reachable with $n$ measurements and the smallest $n$ that reaches a given error $\varepsilon$. It explains, for example, when Monte Carlo or quasi-Monte Carlo methods can beat the curse of dimensionality.