Information, Learning, and Verification

This is the first year funding of a three-year continuing award IRI-9212597. Several problems are to be investigated in the continuation of research on information-based complexity: weak and strong tractability of multivariate problems, weak and strong optimal information, verification, and computational learning theory/information-based complexity for continuous problems. In the first two problems, breaking intractability and unsolvability of multivariate problems are explored in various settings. The concepts of strong tractability and strong optimal information are introduced. For strongly tractable problems the dependence on the number of variables is eliminated. The third problem is verification. Surprisingly, for continuous problems, verification can be exponentially harder than computation. Finally, it has been observed that there are parallels between computational learning theory and information-based complexity. Research is conducted on the similarities and differences between these two areas for continuous problems.//