ABSTRACT Contributions to Information-based Complexity, Image Understanding, and Logic Circuit Design

This work consists of three parts. The first two describe new results In information-based complexity and applications of the general theory to the field of computer vision. The last presents an average case result of a. different sort: the design of a binary comparator. Part I is joint work with G. W. Wasilkowski. In this part, we study approximation of linear functionals on a separable Banach space equipped with a Gaussian measure. We study optimal information and optimal algorithms in average case, probabilistic and asymptotic settings, for a. general error functional. We prove that adaptive information is Dot more powerful than nonadaptive information and that II-spline algorithms, which are linear, are optimal in all three settings. We specialize our results to spaces of functions with continuous rth derivatives, equipped with a Wiener measure. In pa.rticular, we show that the interpolation by the na.tural splines of degree r+ 1 yields the optimal a.lgorithIilll. We apply the general results to the problem of integra.tion. Part II of this work studies the following image understanding problems::2 &amp