On the power of random information
For researchers in numerical analysis and information-based complexity, this work clarifies when random sampling can substitute for optimal design, though it is partly a survey.
The paper studies approximation and integration problems, comparing optimal versus random information, finding that random information is nearly optimal for some problems but significantly worse for others, with new results and a survey of known results.
We study approximation and integration problems and compare the quality of optimal information with the quality of random information. For some problems random information is almost optimal and for some other problems random information is much worse than optimal information. We prove new results and give a short survey of known results.