Uniform approximation of vectors using adaptive randomized information

We study approximation of the embedding ₚᵐ → ∞ᵐ, 1 ≤ p ≤ 2, based on randomized adaptive algorithms that use arbitrary linear functionals as information on a problem instance. We show upper bounds for which the complexity n exhibits only a (loglog m)-dependence. Our results for $p=1$ lead to an example of a gap of order n (up to logarithmic factors) for the error between best adaptive and non-adaptive Monte Carlo methods. This is the largest possible gap for linear problems.