# Tractability of Multivariate Problems: Volume I: Linear Information

Share this page
*Erich Novak; Henryk Woźniakowski*

A publication of the European Mathematical Society

Multivariate problems occur in many applications. These problems are
defined on spaces of \(d\)-variate functions and \(d\) can be
huge—in the hundreds or even in the
thousands. Some high-dimensional problems can be solved efficiently to
within \(\varepsilon\), i.e., the cost increases polynomially in
\(\varepsilon^{-1}\) and \(d\). However, there are many
multivariate problems for which even the minimal cost increases exponentially
in \(d\). This exponential dependence on \(d\) is called
intractability or the curse of dimensionality.

This is the first volume of a three-volume set comprising a
comprehensive study of the tractability of multivariate problems. It is devoted
to tractability in the case of algorithms using linear information and develops
the theory for multivariate problems in various settings: worst case, average
case, randomized and probabilistic. A problem is tractable if its minimal cost
is not exponential in
\(\varepsilon^{-1}\) and \(d\). There are various notions of
tractability, depending on how we measure the lack of exponential dependence.
For example, a problem is polynomially tractable if its minimal cost is
polynomial in \(\varepsilon^{-1}\) and \(d\). The study of
tractability was initiated about 15 years ago. This is the first and only
research monograph on this subject.

Many multivariate problems suffer from the curse of dimensionality when
they are defined over classical (unweighted) spaces. In this case, all
variables and groups of variables play the same role, which causes the minimal
cost to be exponential in \(d\). But many practically important problems
are solved today for huge \(d\) in a reasonable time. One of the most
intriguing challenges of the theory is to understand why this is possible.
Multivariate problems may become weakly tractable, polynomially tractable or
even strongly polynomially tractable if they are defined over weighted
spaces with properly decaying weights. One of the main purposes of this book is
to study weighted spaces and obtain necessary and sufficient conditions on
weights for various notions of tractability.

The book is of interest for researchers working in computational
mathematics, especially in approximation of high-dimensional problems. It may
be also suitable for graduate courses and seminars. The text concludes with a
list of thirty open problems that can be good candidates for future
tractability research.

A publication of the European Mathematical Society (EMS). Distributed within the Americas by the American Mathematical Society.

#### Readership

Graduate students and research mathematicians interested in applications.