Randomized approximation of Sobolev embeddings, II

We study the approximation of Sobolev embeddings by linear randomized algorithms based on function values. Both the source and the target space are Sobolev spaces of non-negative smoothness order, defined on a bounded Lipschitz domain. The optimal order of convergence is determined. We also study the deterministic setting. Using interpolation, we extend the results to other classes of function spaces. In this context a problem posed by Novak and Woźniakowski is solved. Finally, we present an application to the complexity of general elliptic PDE.