  Given a function f: [a,b] -> R, if f(a) < 0 and f(b)> 0 and f is continuous,
the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover,
given a value-oracle for f, an approximate root of f can be computed using the
bisection method, and the number of required evaluations is polynomial in the
number of accuracy digits. The goal of this note is to identify conditions
under which this polynomiality result extends to a multi-dimensional function
that satisfies the conditions of Miranda's theorem -- the natural
multi-dimensional extension of the Intermediate Value Theorem. In general,
finding an approximate root might require an exponential number of evaluations
even for a two-dimensional function. We show that, if f is two-dimensional and
satisfies a single monotonicity condition, then the number of required
evaluations is polynomial in the accuracy. For any fixed dimension d, if f is a
d-dimensional function that satisfies all d^2-d ``ex-diagonal'' monotonicity
conditions (that is, component i of f is monotonically decreasing with respect
to variable j for all i!=j), then the number of required evaluations is
polynomial in the accuracy. But if f satisfies only d^2-d-2 ex-diagonal
conditions, then the number of required evaluations may be exponential in the
accuracy. The case of d^2-d-1 ex-diagonal conditions remains unsolved. As an
example application, we show that computing approximate roots of monotone
functions can be used for approximate envy-free cake-cutting.
