Integration and approximation of multivariate functions: Average case complexity with isotropic Wiener measure (Q1329033)

The paper is concerned with the average complexity of the integration and \(L_2\)-function approximation problems for the class \(F = C([0,1]^d)\) of continuous functions of \(d\) variables. The class \(F\) is endowed with the isotropic Wiener measure (or Brownian motion in Lévy's sense) and the average complexity equals \(\theta(\varepsilon^{-2(1+1/d)})\) for the integration problem and equals \(\theta(\varepsilon^{-2d})\) for the approximation problem. The case of average complexity with respect to the Wiener sheet measure on \(F\) was considered by \textit{H. Woźniakowski} [Bull. Am. Math. Soc., New Ser. 24, No. 1, 185-194 (1991; Zbl 0729.65010)]. The study of the average case setting is motivated by the intractability of the worst case setting, see \textit{J. F. Traub, G. W. Wasilkowski} and \textit{W. Woźniakowski}, Information-based complexity (1988; Zbl 0654.94004), and references therein. An announcement of the present paper appeared in Bull. Am. Math. Soc., New Ser. 28, No. 2, 308-314 (1993; Zbl 0770.41020).