The project focuses on determining the computation power of models of computation over the real numbers such as: (a) linear decision trees; (b) branching programs with linear tests; and (c) combinational circuits of bounded and unbounded fan-in with gates computing real functions, for the computation of Boolean functions. The latter models are also examined from the aspect of approximate and exact computation of real functions. The goal is to prove lower bounds for explicitly defined functions and to study the relations between different complexity measures for these models. This research could lead to new lower bound arguments and it could contribute to the understanding of the interaction between discrete and continuous aspects of computation. In computational learning theory, extensions of previous work on concept learning in on-line learning models are studied, as well as the approximate learning of real functions belonging to classes defined by smoothness or structural properties. In addition, concept learning in structures of first-order logic is examined. These investigations are related to results and methods in PAC learning, information based complexity and finite model theory. Finally, another goal of this project is to extend these formal learnability results to areas often investigated in artificial intelligence.
