Abstract:
We survey recent results on the average case complexity for linear multivariate problems. Our emphasis is on problems defined on spaces of functions of $d$ variables with large $d$. We present the sharp order of the average case complexity for a number of linear multivariate problems as well as necessary and sufficient conditions for the average case complexity not to be exponential in $d$.
Keywords:average case setting, minimal error, Wiener measure, complexity, Hilbert space, linear nultivariate problem, Wiener sheet, Banach space, tractability, tensor product, weighted approximation.
Fulltext:
PDF file (269 kB)