  We study approximation of the embedding $\ell_p^m \rightarrow
\ell_{\infty}^m$, $1 \leq p \leq 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 $(\log\log
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.
