Joseph Traub

Paper #: 09-05-016

The goal of information-based complexity is to create a theory of optimal algorithms and computational complexity for problems with partial, contaminated and priced information, and to apply the results to solving specific problems in various disciplines. The continuous mathematical models which occur in the physical and social sciences and engineering typically have only partial, contaminated, and priced information. Such problems usually have to be solved numerically to within a certain error threshold. Of particular interest are problems in hundreds or thousands of variables. A central issue is vanquishing the resulting "curse of dimensionality." Information-based complexity has been applied to fields ranging from computational finance to quantum computing. This paper traces the history of information-based complexity to the present.

PDF