# Book Details

Search page | Title Index | Author Index

Preface | Table of Contents | Overview | MARC record | Metadata XML | e-Book PDF (2654 KB)*Erich Novak (University of Jena, Germany)*

Henryk Woźniakowski (Columbia University, New York, USA, and University of Warsaw, Poland)

Henryk Woźniakowski (Columbia University, New York, USA, and University of Warsaw, Poland)

#### Tractability of Multivariate Problems

Volume I: Linear InformationISBN print 978-3-03719-026-5, ISBN online 978-3-03719-526-0

DOI 10.4171/026

September 2008, 395 pages, hardcover, 17.0 x 24.0 cm.

68.00 Euro

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 `ε`,
i.e., the cost increases polynomially in `ε`^{−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 of a three-volume set comprising a comprehensive study of the
tractability of multivariate problems.
It is devoted to algorithms using
linear information consisting of arbitrary linear functionals.
The theory for multivariate problems is developed
in various settings: worst case, average case, randomized and
probabilistic. A problem is tractable if its minimal cost is *not*
exponential in `ε`^{−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 `ε`^{−1} and `d`. The study of tractability was
initiated about 15 years ago. This is the first research
monograph on this subject.

Many multivariate problems suffer from the curse of dimensionality
when they are defined over classical (unweighted) spaces.
But many
practically important problems are solved today for huge `d` in a
reasonable time. One of the most intriguing challenges of theory is to
understand why this is possible. Multivariate problems may become tractable
if they are defined over *weighted* spaces with properly
decaying weights. In this case, all variables and groups of variables
are moderated by weights. The main purpose of this book is to study weighted spaces
and to obtain conditions on the weights that are necessary and sufficient
to achieve 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.

*Keywords: *Curse of dimensionality, tractability, high-dimensional numerical problems, worst case setting, average case setting, randomized algorithms, weighted norms, product weights, finite-order weights

#### Further Information

Review in Zentralblatt MATH 1156.65001