Uniform recovery of high-dimensional $C^r$-functions

Abstract

We consider functions on the $d$-dimensional unit cube whose partial derivatives up to order $r$ are bounded by one. It is known that the minimal number of function values that is needed to approximate the integral of such functions up to the error $\epsilon$ is of order $(d/\epsilon {)}^{d/r}$. Among other things, we show that the minimal number of function values that is needed to approximate such functions in the uniform norm is of order $(d^{r/2}/\epsilon {)}^{d/r}$ whenever $r$ is even.