Tractability of tensor product problems in the average case setting

It 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 S_d d≥1, with accuracy ε. If ∑j=j=1 ^∞λ_j ≥ 1 and λ₂ > 0, we know that S is not polynomially tractable iff lim sup _j→∞λ_jj^p =∞ 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 ℓ=lim/j→∞^λjjln ³(j+1), exists. Then S is weakly tractable iff ℓ = 0.