Preliminary list of abstracts

Note: We are using the fantastic MathJax JavaScript library to typeset the mathematics on this web page. You can right-click on a formula to zoom in or to select the rendering engine you like (all under 'Settings'). Under Firefox the default renderer turns out to be MathML (which is quick), but you might prefer the HTML-CSS renderer for more faithful LaTeX rendering. If you encounter any problems with this setup: then please email us!

Click here to go back to the list of abstracts.

Approximation of linear multivariate problems in the randomized setting
Keywords: Multivariate problems; Tractability; Lower Bounds
Thu, 15:45--16:10
  • Wozniakowski, Henryk (Computer Science Department, Columbia university, United States; Institute of Applied Mathematics, University of Warsaw, Poland)

We study approximation of linear operators defined between Hilbert spaces in the randomized setting. We consider algorithms that use $n$ function values or $n$ arbitrary linear functionals. It is known that randomization does not really help and is of the same power as in the worst case case when we may use arbitrary linear functionals. We want to verify when the use of function values in the randomized setting is of the same power as the use of arbitrary linear functionals in the randomized and worst case settings. We provide a number of practically important examples of linear operators and Hilbert spaces for which it is indeed the case, as well as examples for which it is not the case.