Session III.5 - Information-Based Complexity
Tuesday, June 20, 15:00 ~ 15:30
Problems in the worst case approximation of linear operators in the presence of noise
Leszek Plaskota
University of Warsaw, Poland - This email address is being protected from spambots. You need JavaScript enabled to view it.
Information-based complexity (IBC) deals with computational complexity of solving problems for which information is partial, noisy, and priced. Most of the IBC research is however devoted to problems for which information is partial and exact, despite the fact that noise is a frequent guest in real-world computational problems. Moreover, the presence of noise enriches the computational model and leads to interesting theoretical questions. In this talk we present some solved and open problems related to the worst case complexity of approximating linear operators from information contaminated with bounded or Gaussian noise.