Lecture 1: Some old and new results on Information-Based Complexity
Duration: 54 mins 53 secs
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Novak, E
Monday 11th February 2019 - 15:00 to 16:30 |
|---|
| Created: | 2019-02-12 11:15 |
|---|---|
| Collection: | Approximation, sampling and compression in data science |
| Publisher: | Isaac Newton Institute |
| Copyright: | Novak, E |
| Language: | eng (English) |
| Abstract: | 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 ϵ? 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 Ck functions, and results for randomized algorithms |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.93 Mbits/sec | 797.03 MB | View | Download | |
| WebM | 640x360 | 565.85 kbits/sec | 227.53 MB | View | Download | |
| iPod Video | 480x270 | 522.11 kbits/sec | 209.88 MB | View | Download | |
| MP3 | 44100 Hz | 249.79 kbits/sec | 100.50 MB | Listen | Download | |
| Auto * | (Allows browser to choose a format it supports) | |||||