Complexity of multilinear problems in the average case setting (Q1174451)

This is the second part of studies on multilinear problems devoted to the average case setting. The first part [J. Complexity 6, No. 4, 389-408 (1990; Zbl 0712.94001)] deals with the worst case setting. Let \(F_ i\) \((i=1,\dots,k)\) and \(G\) be separable Banach spaces. Denote \(F:= F_ 1\times\cdots\times F_ k\). Let \(S: F\to G\) be a \(k\)-linear operator. The aim is to approximate \(Sf\) for \(f\in F\) knowing only certain information about \(f\). In the average case, \(F\) is equipped with some measure \(\mu\). The error and cost of an algorithm are defined by average performance with respect to \(\mu\). If \(G\) is a Hilbert space, then it is shown that the spline algorithms are optimal. If \(G\) is a Banach space, then the multilinear problem can be reduced to linear subproblems. Optimality properties of spline algorithms are established.