The randomized information complexity of elliptic PDE

We study the information complexity in the randomized setting of solving a general elliptic PDE of order 2m2m in a smooth, bounded domain Q⊂RdQ⊂Rd with smooth coefficients and homogeneous boundary conditions. The solution is sought on a smooth submanifold M⊆QM⊆Q of dimension 0⩽d1⩽d0⩽d1⩽d, the right-hand side is supposed to be in Cr(Q)Cr(Q), the error is measured in the L∞(M)L∞(M) norm. We show that the nth minimal error is (up to logarithmic factors) of ordern-min(r+2m)/d1,r/d+1/2.For comparison, in the deterministic setting the n  th minimal error is of order n-r/d,n-r/d, for all d1d1.