Introduction
This seminar is run during the Spring semester, 2011. In this class, we learn the theory and applications of Information Based Complexity: the branch of computational complexity that deals with the intrinsic difficulty of the approximate solution of problems for which the information is partial, noisy and priced. Our studies are mainly based on the book - Selected Topics in Approximation and Computation.
Topics
General concepts about information, algorithm and computational method
Optimal information, optimal algorithm and the corresponding complexity
Instructor
Christopher SikorskiSchedule
| When | Where | Topic |
|---|---|---|
| 01/12 Wed. 02:00PM | Kris's office | organizational meeting |
| 01/19 Wed. 02:00PM | Kris's office | History of Information Based Complexity |
| 01/26 Wed. 03:00PM | Graphics Annex | Introduction to the integral example in Chapter 7 |
| 02/09 Wed. 02:40PM | Kris's office | Review of the example and introduction to more general concepts of information, algorithm and computational method |
| 02/23 Wed. 02:40PM | Kris's office | Optimal information, complexity issues and optimal complexity methods |
| 03/09 Wed. 02:40PM | Kris's office | Generalization of information, algorithm and computational method; radius and diameter; adversary principle. |
| 03/16 Wed. 02:40PM | Kris's office | Interpolatory algorithms and introduction to linear problems |
| 03/30 Wed. 02:40PM | Kris's office | Proof of a linear theory about unsolvability and introduction to nonlinear problems |
| 04/06 Wed. 02:40PM | Kris's office | Continue the discussion about the Borsuk - Ulam's Lemma on antipoles and the proof of the solvability of linear problems with nonlinear information |
| 04/13 Wed. 02:00PM | WEB L104 | Go to attend the SCI seminar during which the Nobel Laureate Richard J. Roberts will give a talk on genomes, computers and experimentation in biology. |
| 04/20 Wed. 02:40PM | Kris's office | Designing optimal algorithms for linear problems and introduction to unitary space and scalar product in our class F. |
| 04/27 Wed. 02:40PM | Kris's office | Continue the proof of designing optimal algorithms and discuss the signal reconstruction example |