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) |