Randomized complexity of vector-valued approximation (Q7012111)

This interesting paper deals with the subject of random complexity of vector-valued approximation. A well known and very difficult problem in this circle of problems asks if there exists a constant \(c>0\) such for all linear problems, the randomized non-adaptive and adapative \(n,\, n\geq 1\) minimal errors (and hence complexity) can deviate by at most a factor of \(c\). This problem was solved in [\textit{S. Heinrich}, J. Complexity 82, Article ID 101823, 31 p. (2024; Zbl 1535.65009)] in which it was shown that there are instances where the gap between non-adaptive and adapt randomized minimial errors can be up to log factors, of the order \(n^{1/8}\). For maximal possible deviation, the author shows in this paper that the gap is up to log terms \(\sqrt{n}\) for certain situations in vector valued approximation.\N\NFor the entire collection see [Zbl 1552.65006].