We mainly study multivariate (uniform or Gaussian) integration defined for
integrand spaces F_d
such as weighted Sobolev spaces of functions of d variables
with smooth mixed derivatives. The weight g_j moderates the behavior
of functions with respect to the jth variable. For g_j=1,
we obtain the classical Sobolev spaces whereas for decreasing g_j's
the weighted Sobolev spaces consist of functions with diminishing dependence
on the jth variables. We study the minimal errors of quadratures
that use n function values for the unit ball of the space F_d.
It is known that if the smoothness
parameter of the Sobolev space is one, then the minimal error is the same
as the discrepancy. Let n(\e,F_d) be the smallest n for which we reduce the
initial error, i.e., the error with n=0, by a factor \e.
The main problem studied in this paper is to
determine whether the problem is intractable, i.e., whether
n(\e,F_d) grows faster than polynomially in \e^{-1} or d.
In particular, we prove intractability of integration
(and discrepancy) if \limsup_d \sum_{j=1}^d g_j/\ln d = \infty.
Previously, such results were known only for restricted classes of quadratures.
For \g_j = 1, the following bounds hold for discrepancy
a) with boundary conditions
1.0628^d (1+o(1)) \le n(\e,F_d) \le 1.5^d \e^{-2},
as d \to \infty,
b) without boundary conditions
1.0463^d (1+o(1)) \le n(\e,F_d) \le 1.125^d \e^{-2},
as d \to \infty.
These results are obtained by analyzing arbitrary linear tensor
product functionals I_d defined over weighted tensor product
reproducing kernel Hilbert spaces F_d of functions of d variables.
We introduce the notion of a decomposable
kernel. For reproducing kernels that have a decomposable part
we prove intractability of all I_d with
non-zero subproblems with respect to the decomposable part of the kernel,
as long as the weights satisfy the condition mentioned above.
Submitted for publication.