Date:	Mon, September 27, 2010
Time:	17:15
Place:	Research II Lecture Hall

Abstract: We study numerical problems, like integration and approximation, defined for classes F_d of functions of d variables, say of the form f: [0,1]^d --> R . The problem is polynomially tractable if the computing time is bounded by C*d^q*epsilon^{-p} for all natural d, where epsilon >0 is the error bound.

We start with an example that shows that the order of convergence can be excellent and still the problem is not polynomially tractable. Hence we have to reconsider most of the classical error bounds in numerical analysis.

We deal mainly with the question of how we can obtain tractability.

• Can tractability be obtained by strong smoothness assumptions?
• Can tractability be obtained by ``sparsity'', ``finite order weights'' or ``special structure''?
• Can tractability be obtained by randomization?

The presentation is based on joint work with Henryk Wozniakowski, in particular our book ``Tractability of Multivariate Problems'', European Math. Society. Volume I appeared in 2008, Volume II in 2010.