No label defined (Q4029604)

[For the entire collection see Zbl 0745.00057.] The goal of this article is to present a selective introduction to the field of information-based complexity and to describe the seesaw nature of results in the last decade on the extent to which linear problems have linear optimal algorithms. The approach we take will certainly not do justice to the breadth of ideas, techniques, and applications that are coming into play in the general theory. Instead, we will take a direct route to the results on linear optimal algorithm, pausing occasionally to survey the pleasing way in which ideas from linear algebra and (functional) analysis are used. We mention some other theoretical and applied topics currently under investigation in the theory of optimal algorithms.