skip to content

Lecture 1: Some old and new results on Information-Based Complexity

Presented by: 
Erich Novak
Monday 11th February 2019 - 15:00 to 16:30
INI Seminar Room 1

We give a short introduction to IBC and present some basic definitionsand a few results. The general question is: How many function values (or values of other functionals) of $f$ do we need to compute $S(f)$ up to an error $\epsilon$? Here $S(f)$ could be the integral or the maximum of $f$.
In particular we study the question: Which problems are tractable? When do we have the curse of dimension?
 In the second talk we discuss complexity results for numerical integration. In particular we present results for the star discrepancy, the curse of dimension for $C^k$ functions, and results for randomized algorithms


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons