Average Case $(s, t)$-weak tractability of non-homogenous tensor product problems
Provides a theoretical characterization of tractability for a class of multivariate problems, which is incremental for researchers in information-based complexity.
The paper establishes necessary and sufficient conditions for $(s, t)$-weak tractability of non-homogeneous tensor product problems in the average case setting, applicable to several covariance kernels including Euler and Wiener integrated processes.
We study $d$-variate problem in the average case setting with respect to a zero-mean Gaussian measure. The covariance kernel of this Gaussian measure is a product of univariate kernels and satisfies some special properties. We study $(s, t)$-weak tractability of this multivariate problem, and obtain a necessary and sufficient condition for $s>0$ and $t\in(0,1)$. Our result can apply to the problems with covariance kernels corresponding to Euler and Wiener integrated processes, Korobov kernels, and analytic Korobov kernels.