Tractability of Multivariate Problems, vol. I
This is a book - the first one of three planned volumes - on recent research in the field of computational mathematics, dealing with high dimensional multivariate problems. Problems of information complexity discussed in the book appear in several areas of mathematics and physics: computation of path integrals (Feynman-Kac formulae), global optimization of functions of very many variables (like in image processing - often using simulated annealing algorithms), when solving the many body Schrödinger equation and many other situations. The exponential dependence of the “cost” of the computation on d (where d denotes the number of variables) means the “intractability” (or curse of dimensionality) of the problem. A simple example of intractability (in d) is integration of a smooth function of d variables (to a given precision ε). Depending on d and ε, several types of (in)tractability can be defined and the book offers a careful analysis of various situations. The problems discussed in the book range from computer science to abstract functional analysis and many interesting open problems are presented here.