Given a function $f: [a,b] \to \mathbb{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 paper 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 of $f$ might require an exponential number of evaluations even for a two-dimensional function. We show that, if $f$ is two-dimensional, and at least one component of $f$ is monotone, an approximate root of $f$ can be found using a polynomial number of evalutaions. This result has applications for computing an approximately envy-free cake-cutting among three groups.

翻译：暂无翻译