A survey of average case complexity for linear multivariate problems
- 29 April 2009
- journal article
- Published by Allerton Press in Russian Mathematics
- Vol. 53 (4) , 1-14
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
This publication has 46 references indexed in Scilit:
- On the power of standard information for multivariate approximation in the worst case settingJournal of Approximation Theory, 2009
- Multivariate approximation in the worst case setting over reproducing kernel Hilbert spacesJournal of Approximation Theory, 2008
- Applicability of Smolyak's Algorithms to Certain Banach Spaces of Multivariate FunctionsJournal of Complexity, 2002
- Integration and approximation in arbitrary dimensionsAdvances in Computational Mathematics, 2000
- Irregularities of Distribution1987
- Gaussian measure in Hilbert space and applications in numerical analysisRocky Mountain Journal of Mathematics, 1972
- A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by SplinesThe Annals of Mathematical Statistics, 1970
- On Some Problems Concerning Brownian Motion in Lévy’s SenseTheory of Probability & Its Applications, 1967
- Theory of reproducing kernelsTransactions of the American Mathematical Society, 1950
- Zur mechanischen QuadraturZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, 1933