This proposal involves complexity analysis and the development of optimal algorithms for the solution of nonlinear problems. Unlike most current research in complexity which is discrete in nature, the problems considered in this proposal are (piecewise) continuous functions of one or more real variables. The tools for complexity analysis of these problems thus differ from traditional complexity analysis and are based on the ideas of information-based complexity. The development of an upper bound on problem complexity is similar to classical numerical analysis (and may in fact borrow from previous work therein). The derivation of lower bounds on a problem's complexity is one of the novel aspects of this research, and can be roughly described as follows: Using mathematical techniques, one develops a set of functions with different solutions to the problem but which are indistinguishable using a given amount of information. Unless this set of functions is a singleton no algorithm can solve the problem. This provides lower bounds on the amount of information required to solve the problems, which in turn bounds the problem complexity from below. While the concepts are simple, the derivation of a particular bound is generally quite difficult, and often provides insight useful for achieving better upper bounds. The nonlinear problems addressed in this research will include both worst-case and "average"-case analysis of the computation of topological degree in one or more dimensions, root-finding for Lipschitz function in one two and three dimensions, and segmentation/reconstruction of overlapping functions from function values (with restrictions from computer vision). These problems have both theoretical and practical importance, and the techniques developed for their analysis should be useful elsewhere.
