Prof. Henryk Woźniakowski

"Tractability of Multivariate Numerical Problems"

There is a branch of computational complexity that studies complexity of continuous problems for which only partial information is available. This branch is called information-based complexity and uses the real number model of computation. Typical applications involve multivariate functions of d variables. Partial information is often defined as finitely many function values. Examples of typical problems include multivariate integration and approximation, solution of ordinary or partial dirential equations, integral equations, optimization, path integration and solving nonlinear equations. Such problems can be solved only approximately with error ε. The complexity is defined as the minimal cost over the class of all algorithms that solve the problem with error at most ε. Depending on how the cost and error are defined, the complexity is studied in dirent settings including the worst case, average case, probabilistic, randomized and quantum settings.
The dependence on ε has been studied for years, whereas the study of the dependence on d is relatively new. The dependence on d is especially relevant when d is large. This is the case for many practical problems, such as problems in financial mathematics and mathematical economics, where d is in the hundreds or even in the thousands.
Many important multivariate problems have been proven to be intractable in the worst case deterministic setting for classical spaces such as Sobolev or Korobov spaces. This means that their complexity is an exponential function in ε^-1 or d. In the latter case, this is called the "curse of dimensionality". Examples of intractable problems include the problems mentioned above.
To break intractability of the worst case deterministic setting we either have to settle for a weaker assurance or use additional knowledge about the problem. One way is to settle for a randomized or average case setting. For multivariate integration, it is well known that the Monte Carlo algorithm breaks intractability in the randomized setting. Intractability is also broken in the average case setting for the class of continuous functions equipped with the classical Wiener sheet measure. For multivariate approximation the situation is more intriguing. This problem is intractable in both the worst case deterministic and randomized settings. Intractability is broken in the average case setting for the class of continuous functions equipped with the Wiener sheet measure, but this problem is still intractable if the Wiener sheet measure is replaced by the Wiener isotropic measure.
Another way of breaking intractability is to use additional knowledge about the problem which is currently a very intense research area of information-based complexity. A major example of such additional knowledge is when we know that functions depend on successive variables or on groups of variables in a diminishing way. For problems such as multivariate integration and approximation defined on tensor product Sobolev and Korobov classes, we know necessary and suchcient conditions on the space weights to guarantee to break intractability even in the worst case deterministic setting.