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}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 SdSd, d≥1d≥1, with accuracy εε. If ∑j=1∞λj<1 and λ2>0λ2>0, we know that SS is not polynomially tractable iff lim supj→∞λjjp=∞lim supj→∞λjjp=∞ for all p>1p>1. Thus we settle the open problem by showing that SS is weakly tractable iff ∑j>nλj=o(ln−2n)∑j>nλj=o(ln−2n). In particular, assume that ℓ=limj→∞λjjln3(j+1), exists. Then SS is weakly tractable iff ℓ=0ℓ=0.