The project addresses the complexity of algorithms for approximately solved problems. In contrast to discrete complexity theory this investigation deals with problems that are continuous in nature and which cannot be solved exactly in finite time. The cost of an approximate algorithm depends on its quality (error), and on the form of its input, which is composed by a number of observations of some otherwise unknown quantity. The problems to be investigated include the "average case" solution of nonlinear equations, the effects of various kinds of sampling in the approximation of linear operators, and the development and implementation of Monte Carlo-type of algorithms for various classes of integrands. The analysis of these problems involves the derivation of an optimal error algorithm followed by its complexity analysis. Often, techniques from complexity theory, approximation theory and results for other similar, or related, problems can be combined to obtain tight error and complexity estimates. Nevertheless, in some cases the only possibility is to modify a known algorithm in order to obtain another with an improved performance. The derivation of lower bounds in usually difficult, and the modifications aim to expose characteristics of the problems and properties of the algorithms. The problems of interest here and the techniques that will be applied for their solution are important not only to complexity theory but to other areas of applied science as well.
