Algorithms and Complexity for some Multivariate Problems
It provides theoretical insights into the minimal information needed to solve high-dimensional problems, benefiting researchers in numerical analysis and computational mathematics.
The paper studies the information complexity of multivariate problems such as function approximation, numerical integration, global optimization, and dispersion, presenting optimal algorithms and new complexity bounds.
We study multivariate problems like function approximation, numerical integration, global optimization and dispersion. We obtain new results on the information complexity $n(\varepsilon,d)$ of these problems. The information complexity is the amount of information (e.g. the number of function values) that is needed to solve the $d$-dimensional problem up to a prescribed error $\varepsilon>0$. We present optimal algorithms for some of these problems. An extended abstract can be found in the section "Introduction and Results".