### Mathematics Colloquium

# Erich Novak

### (Universität Jena)

## "Tractability of multivariate problems"

** 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.