Tractability of tensor product problems in the average case setting

AbstractIt has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem S={Sd} in the average case setting to be weakly tractable but not polynomially tractable. As a result of the tensor product structure, the eigenvalues of the covariance operator of the induced measure in the one-dimensional problem characterize the complexity of approximating Sd, d≥1, with accuracy ε. If ∑j=1∞λj<1 and λ2>0, we know that S is not polynomially tractable iff lim supj→∞λjjp=∞ for all p>1. Thus we settle the open problem by showing that S is weakly tractable iff ∑j>nλj=o(ln−2n). In particular, assume that ℓ=limj→∞λjjln3(j+1), exists. Then S is weakly tractable iff ℓ=0