View abstract

Session III.5 - Information-Based Complexity - Semi-plenary talk

Wednesday, June 21, 15:00 ~ 16:00

Lower bounds for numerical integration and approximation

Jan Vybiral

Czech Technical University, Czech Republic   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We review recent methods, which allow to prove lower bounds for numerical integration and approximation of functions from a reproducing kernel Hilbert space $H$. Quite naturally, the technique of a bump function fails if $H$ contains only very smooth (i.e., analytic) functions. We show that it is also not optimal, if the functions from $H$ are barely continuous. In this case, optimal lower bounds can be obtained by a completely different method, which is based on a certain variant of the Schur multiplication theorem on a coordinate-wise product of positive semi-definite matrices. This approach allowed to settle an old problem of E. Novak on intractability of numerical integration of multivariate trigonometric polynomials with degree at most one in each variable. Furthermore, in a series of papers jointly with Aicke Hinrichs and David Krieg (both JKU Linz, Austria) and Erich Novak (FSU Jena, Germany) we developed this tool to an universal instrument for lower bounds on numerical integration.

Joint work with Aicke Hinrichs (JKU Linz, Austria), David Krieg (JKU Linz, Austria) and Erich Novak (FSU Jena, Germany).

View abstract PDF