Session III.5 - Information-Based Complexity
Tuesday, June 20, 15:30 ~ 16:00
Worst case tractability of linear problems in the presence of noise: linear information
Pawel Siedlecki
University of Warsaw, Poland - This email address is being protected from spambots. You need JavaScript enabled to view it.
We study the worst case tractability of multivariate linear problems defined on separable Hilbert spaces. Information about a problem instance consists of noisy evaluations of arbitrary bounded linear functionals, where the noise is either deterministic or random. The cost of a single evaluation depends on its precision and is controlled by a cost function. We establish mutual interactions between tractability of a problem with noisy information, the cost function, and tractability of the same problem, but with exact information.
Joint work with Leszek Plaskota (University of Warsaw, Poland).