  We study the $L_1$-approximation of $d$-variate monotone functions based on
information from $n$ function evaluations. It is known that this problem
suffers from the curse of dimensionality in the deterministic setting, that is,
the number $n(\varepsilon,d)$ of function evaluations needed in order to
approximate an unknown monotone function within a given error threshold
$\varepsilon$ grows at least exponentially in $d$. This is not the case in the
randomized setting (Monte Carlo setting) where the complexity
$n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ (modulo logarithmic terms)
only. An algorithm exhibiting this complexity is presented. Still, the problem
remains difficult as best known methods are deterministic if $\varepsilon$ is
comparably small, namely $\varepsilon \preceq 1/\sqrt{d}$. This inherent
difficulty is confirmed by lower complexity bounds which reveal a joint
$(\varepsilon,d)$-dependency and from which we deduce that the problem is not
weakly tractable.
