Complexity lower bounds for approximation algebraic computation trees

Felipe Cucker^{∗}^{†}

Department of Mathematics City University of Hong Kong 83 Tat Chee Avenue, Kowloon HONG KONG

                e-mail: macucker@math.cityu.edu.hk

Dima Grigoriev^{∗} IMR Université de Rennes I Campus de Beaulieu, Rennes 35042 FRANCE

                e-mail: dima@maths.univ-rennes1.fr

Abstract We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.

The goal of this paper is to prove lower bounds for approximated computations. As it is customary for lower bounds, we consider some form of algebraic tree as our computational model (cf. [Bürgisser, Clausen, and Shokrollahi 1996] or [Blum, Cucker, Shub, and Smale 1998] for algebraic trees). But, unlike the usual proofs of lower bounds, which deal with decision problems, we will consider computations of real functions. That is, we consider trees computing functions f : IR^{n} → IR and, also unlike the usual results on lower bounds, we will allow for approximate computations. To understand the nature of our results let us look first at an example.

Example 1 Given a strictly convex compact polygon P ⊂ IR^{2} consider the function f : IR^{2} → IR defined by

f(c) = max_{x∈P}⟨c, x⟩^{2}.

∗This work was done while both authors were at MSRI. We would like to thank the institute for its support.

†Partially supported by CERG grants.

Obviously, there is a partition of IR^{2} into a finite number of regions V_{i} and for each such region there is a vertex v_{i} of P such that f(c) = ⟨c, v_{i}⟩^{2} for all c ∈ V_{i}.

Let T be an algebraic computation tree computing f of Example 1. Then the number of leaves of T is at least the number of 2-dimensional regions V_{i} with pairwise different v_{i}. This follows from the fact that two different polynomials in IR[x, y] can not coincide, as functions, on an open subset of IR^{2}. Therefore, since computation trees are binary, we have that the depth of T is at least the log_{2} of this number. This argument is independent of the fact that the input space is IR^{2} (any IR^{n} could be considered instead; just replace polygon by polyhedra and IR[x, y] by IR[x_{1}, …, x_{n}]). We intend to replicate it for approximate computations.

Now consider a tree T which computes a δ-approximation of f in the sense that the output T (c) satisfies |f(c) − T (c)| ≤ δ for all c ∈ IR^{2}.

If δ ≠ 0 a lower bound like the one above is no longer valid. To see why, consider a regular n-sided polygon inscribed in the unit circunference centered at the origin. For large n the polygon becomes “close” to the circumference and for n large enough f(c) is δ-approximated by ∥c∥^{2} = c_{1}^{2} + c_{2}^{2}. And this function can be computed with only three operations. So the log_{2} n bound above is far to apply.

Thus, in order to obtain meaningfull lower bounds one needs to impose some condition on the value of δ. We devote the next section to define the main concepts of the paper and to state our main theorem, where this condition is made explicit. In Section 3 we extend our main result to round-off trees i.e., trees whose arithmetic operations are subject to some form of error. Finally, in Section 4, we briefly discuss extensions to other settings such as randomized or parallel trees.

1 Piecewise Polynomial Functions and Round-off Computation Trees

In this paper we will only deal with trees whose computation nodes perform additions, subtractions or multiplications.^{1} It is immediate to prove that such a tree (with exact arithmetic) computes a very specific kind of functions, which we describe in the next definition.

Definition 1 A function f : IR^{n} → IR is called piecewise polynomial if there exists a finite partition IR^{n} = ∪_{i}V_{i} of IR^{n} into semi-algebraic sets V_{i} and for each i a polynomial f_{i} ∈ IR[x_{1}, …, x_{n}] such that f_{|V_{i}} = f_{i}.

Without loss of generality we will assume that if i ≠ j then f_{i} ≠ f_{j}.

The function f of Example 1 is piecewise polynomial. Another example of this kind of function is provided by quantifier elimination in the theory of the reals. Such a procedure defines a piecewise polynomial function by associating, to each tuple of coefficients of an input formula, a vector of coefficients of an equivalent quantifier-free formula.

1The extension of our results to the case of trees allowing divisions is an open problem.

Apparently, computation of piecewise polynomial (or more generally, rational) functions was considered for the first time over the complex numbers rather than over the reals, as in our case, by Strassen [1983] for the problem of computing GCDs of univariate polynomials.

Before defining what we mean by approximation we emphasize that we are considering computation trees rather than decision trees. In particular we recall that, associated to any leaf η of a computation tree T, there is a polynomial g_{η} ∈ IR[x_{1}, …, x_{n}] such that, for any input x ∈ IR^{n} which reaches η in the course of the computation, the output T (x) of T coincides with g_{η}(x) (cf. [Blum, Cucker, Shub, and Smale 1998] for details).

Definition 2 Let T be an algebraic computation tree with input space IR^{n} and output space IR, and let f : IR^{n} → IR be a function.

We say that T approximates f with absolute accuracy δ if for every input x ∈ IR^{n} the output T (x) of T satisfies |T (x) − f(x)| ≤ δ.

We say that T approximates f with relative accuracy δ if for every input x ∈ IR^{n} the output T (x) of T satisfies |T (x) − f(x)| ≤ δ|f(x)|.

Remark 1

1) Approximate algorithms for a problem are a current practice to improve the efficiency over the known algorithms computing the exact solutions of that problem.

2) To the best of our knowledge very little is know on lower bounds for approximate (or round-off) computations. A worth noting exception is a paper by Renegar [Renegar 1987] which gives lower bounds for approximating zeros of univariate polynomials.

We now describe the condition we will impose on δ in order to obtain lower bounds for the depth of approximate computations. This condition takes the form of a bound δ ≤ Γ where Γ is a quantity depending only on the piecewise function f (rather than on the tree). We actually provide a family of conditions parameterized by a positive parameter τ.

Let τ > 0. If f is piecewise polynomial we define

w(τ) = #{i | V_{i} contains an n-dimensional cube of side τ}.

For the rest of this paper we assume that τ satisfies w(τ) > 0. Let

B_{τ} = inf{b ∈ IR | there exist cubes as above which are contained in [−b, b]^{n}}.

Denote by I_{τ} the set of indices i satisfiying the condition in the definition of w(τ) and let

d_{τ} = max_{i∈I_{τ}} degree (f_{i})  and  C_{τ} = min_{{i≠j \atop i,j∈I_{τ}}} ∥f_{i} − f_{j}∥_{∞}

where polynomials are identified with their vectors of coefficients. Define

Γ_{τ} = \frac{C_{τ}}{2} (\frac{2^{\frac{(Dτ −1)^{2}}{4} −1}}{(D_{τ} + 1)B_{τ}} (\frac{τ}{N}_{τ} )^{\frac{Dτ (Dτ +1)}{2}} )^{n}

where D_{τ} = max{d_{τ} , w(τ)}, N_{τ} = w(τ)D_{τ} n + 1, and

B_{τ} = \{ \begin{matrix}B_{τ}^{D_{τ}^{2}} & if B_{τ} ≥ 1 \\ B_{τ}^{D_{τ} −1} & if B_{τ} < 1. \end{matrix}

We can now state our main theorem.

Theorem 1 If T approximates a piecewise polynomial function f with absolute accuracy δ and

δ ≤ Γ_{τ}

then the depth k of T satisfies

k ≥ log_{2} w(τ).

In proving Theorem 1 the following lemma is essential.

Lemma 1 Let f ∈ IR[x_{1}, …, x_{n}] with degree_{x_{i}}(f) ≤ d and M = ∥f∥_{∞}. Let b_{1}, …, b_{n} ∈ IR, |b_{i}| ≤ B, N ∈ IN, N > d, and consider the uniform grid \overline{S} with mesh τ/N in the cube

∏_{i=1}^{n}[b_{i} − τ, b_{i}].

Let S ⊆ \overline{S} with |S| = s. If

s > s_{n} = N^{n} (1 − (1 − \frac{d}{N} )^{n}) = N^{n} − (N − d)^{n}

then there exists x ∈ S such that

|f(x)| > α = M (\frac{2^{\frac{(d−1)^{2}}{4} −1}}{(d + 1)B} (\frac{τ}{N} )^{\frac{d(d+1)}{2}} )^{n}

where

B = \{ \begin{matrix}B^{d^{2}} & if B ≥ 1 \\ B^{d−1} & if B < 1. \end{matrix}

Proof. By induction on n.

Base case, n = 1. In this case, s_{1} = d, so assume there is a subset S_{0} of \overline{S} having d + 1 points w_{0}, …, w_{d} in \overline{S} such that |f(w_{i})| ≤ α for i = 0, …, d. Then, interpolating f at these points we express each coefficient of f as a fraction

\frac{∑_{x∈S_{0}} a_{x}f(x)}{Δ}

where

Δ = ∏_{{w_{i},w_{j}∈S_{0} \atop 0≤j<i≤d}}(w_{i} − w_{j})

is the determinant of the Vandermonde matrix

V = ( \begin{matrix}1 & w_{0} & w_{0}^{2} & … & w_{0}^{d} \\ 1 & w_{1} & w_{1}^{2} & … & w_{1}^{d} \\ ⋮ & & & & ⋮ \\ 1 & w_{d} & w_{d}^{2} & … & w_{d}^{d} \end{matrix} )

and a_{x} are the determinants of suitable minors of V. The smallest possible value of |Δ| occurs when w_{0}, …, w_{d} are consecutive in S (i.e. w_{i} − w_{i−1} = τ/N) and in this case we have

|Δ| ≥ ∏_{i=1}^{d} (\frac{iτ}{N} )^{d−i+1} = (\frac{τ}{N} )^{\frac{d(d+1)}{2}} ∏_{i=1}^{d} i!.

On the other hand, by bounding each of the d! terms in the definition of determinant we have |a_{x}| ≤ B^{d^{2}}d! if B ≥ 1 and |a_{x}| ≤ B^{d−1}d! if B < 1. That is, |a_{x}| ≤ Bd!. Therefore, the absolute value of each coefficient of f is less than

\frac{(d + 1)Bd!α}{(\frac{τ}{N} )^{\frac{d(d+1)}{2}} ∏_{i=1}^{d} i!} ≤ \frac{(d + 1)Bα}{(\frac{τ}{N} )^{\frac{d(d+1)}{2}} 2^{\frac{(d−1)^{2}}{4} −1}}

the last inequality since ∏_{i=1}^{d} i! ≥ 2^{\frac{d^{2}}{4} −1} for all d ≥ 1. But then

M < \frac{(d + 1)Bα}{(\frac{τ}{N} )^{\frac{d(d+1)}{2}} 2^{\frac{(d−1)^{2}}{4} −1}}

which is in contradiction with the definition of α.

Induction step, n ≥ 2. Write f = ∑_{I} f_{I}X^{I} where f_{I} ∈ IR[x_{n}] and X^{I} is a monomial in x_{1}, …, x_{n−1}. Now, take f_{I_{0}} such that ∥f_{I_{0}}∥_{∞} = M. By the base of the induction, for all but at most d points x in the set

L = \{b_{n} − τ, b_{n} − τ + \frac{τ}{N} , b_{n} − τ + \frac{2τ}{N} , …, b_{n} − τ + \frac{Nτ}{N} = b_{n}\}

we have

|f_{I_{0}}(x)| > \frac{M (2^{\frac{(d−1)^{2}}{4} −1} \frac{τ}{N} )^{\frac{d(d−1)}{2}}}{(d + 1)B} .  (1)

Therefore, there are more than s_{n}−dN^{n−1} points in S whose last coordinate satisfies (1). We conclude that there exists one such point x^{∗} ∈ L such that, moreover,

|S ∩ \{x_{n} = x^{∗}\}| ≥ \frac{s_{n} − dN^{n−1}}{N − d} = s_{n−1}.

Now apply the inductive hypothesis to the polynomial f_{|x_{n}=x^{∗}} ∈ IR[x_{1}, …, x_{n−1}] using that

∥f_{|x_{n}=x^{∗}}∥_{∞} > \frac{M (2^{\frac{(d−1)^{2}}{4} −1} \frac{τ}{N} )^{\frac{d(d−1)}{2}}}{(d + 1)B}

and the conclusion follows. □

2 Proof of Theorem 1

Recall that I_{τ} is the set of indices i satisfiying the condition of the definition of w(τ), D_{τ} = max{w(τ), d_{τ} }, and N_{τ} = w(τ)D_{τ} n + 1. Let i ∈ I_{τ} and consider the grid \overline{S} ⊂ V_{i} as in Lemma 1. We say that a leaf η of T is attached to V_{i} if η is reached by at least N_{τ}^{n}/w(τ) points of \overline{S}.

We claim that one leaf of T can not be attached to two different sets V_{i}. From this claim it follows that k ≥ log_{2} w(τ). Indeed, if k < log_{2} w(τ) then |Leaves(T)| < w(τ) and, by the pigeonhole principle, there is a leaf of T attached to V_{i}. So, every V_{i} has a leaf attached to it. And, by hypothesis, each leaf of T is attached to at most one V_{i}. But then |Leaves(T)| ≥ w(τ) and therefore, k ≥ log_{2} w(τ).

To prove the claim, assume that there exist sets V_{i} and V_{j}, i ≠ j ∈ I_{τ}, such that a leaf η is attached to both of them. Let g_{η} be the polynomial computed along the branch leading to η and C′ = ∥f_{i} − f_{j}∥_{∞}. Then either ∥f_{i} − g_{η}∥_{∞} ≥ C′/2 or ∥f_{j} − g_{η}∥_{∞} ≥ C′/2. We can assume, w.l.o.g., that the first inequality holds.

Let S ⊂ \overline{S} be the set of points reaching the leaf η. Then,

|S| ≥ \frac{N_{τ}^{n}}{w(τ)}.

Since N_{τ} > w(τ)D_{τ} n, we have

|S| > N_{τ}^{n} \frac{D_{τ} n}{N_{τ}} = N_{τ}^{n−1}D_{τ} n ≥ N_{τ}^{n} − (N_{τ} − D_{τ})^{n}.

Thus we can apply Lemma 1 to the polynomial f = f_{i} − g_{η} with M = C′/2, d = D_{τ} and B = B_{τ} and we deduce that there is a point x ∈ S such that

|f_{i}(x) − g_{η}(x)| > \frac{C′}{2} (\frac{2^{\frac{(Dτ −1)^{2}}{4} −1}}{(D_{τ} + 1)B_{τ}} (\frac{τ}{N}_{τ} )^{\frac{Dτ (Dτ +1)}{2}} )^{n} ≥ Γ_{τ}

since C′ ≥ C_{τ}. But this, together with the hypothesis on Γ_{τ}, contradicts the fact that |T (x) − f_{i}(x)| ≤ δ. □

A lower bound for relative approximations easily follows from the proof of Theorem 1. Let

H_{τ} = max_{x∈[−B_{τ} ,B_{τ}]^{n}} |f(x)|.

Corollary 1 If T approximates a piecewise polynomial function f with relative accuracy δ and

δ ≤ \frac{Γ_{τ}}{H_{τ}}

then the depth k of T satisfies

k ≥ log_{2} w(τ).
□

Remark 2 In the sequel we will state our results only for approximations with absolute accuracy δ. Results for those with relative accuracy δ, such as Corollary 1, follow immediately from the former.

Remark 3 The lower bound in Theorem 1 (or that in Corollary 1) is on the depth of T. A more involved issue is the consideration of the topological complexity of f (cf. [Smale 1987] for this concept, see also [Vassiliev 1992]), i.e. the number of leaves of T. This number is essentially the amount of branching necessary for solving the problem. In our discussion of Example 1 we saw that the topological complexity of f is at least the number of 2-dimensional regions V_{i} with pairwise different v_{i} which is at least w(τ) for each τ > 0.

For the problem MAX, consisting of finding the largest coordinate of an input x ∈ IR^{n} and for which the number of pieces is n, the question of the topological complexity is open (see [Grigoriev, Karpinski, and Yao 1998] for the discussion and the exponential lower bound for ternary rathen than the usual binary computation trees).

Implicit in the proof of Theorem 1 is the fact that, if k = log_{2} w(τ), then the topological complexity of T, TC(T), satisfies TC(T) ≥ w(τ). It is unclear to us whether one can trade topological for arithmetical complexity, that is, whether one can reduce the topological complexity of an approximated computation at the expense of increasing the degree of the computed polynomials. We can prove, however, a trade-off between these complexities (and the approximation accuracy δ). Let T be an algebraic computation tree and g_{η} the polynomial computed at leaf η. Define

d_{T} = max_{η a leaf of T} degree (g_{η}).

Note that d_{T} ≤ 2^{k} where k is the depth of T. Now define D_{(τ,T)} = max{d_{τ} , d_{T} } and

Γ_{(τ,T)} = \frac{C_{τ}}{2} (\frac{2^{^{\frac{(D_{(τ,T)}−1)^{2}}{4}} −1}}{(D_{(τ,T)} + 1)B_{(τ,T)}} (\frac{τ}{N}_{τ} )^{\frac{D_{(τ,T)}(D_{(τ,T)}+1)}{2}} )^{n}

with B_{(τ,T)} as in Section 1. The arguments of Theorem 1 yield the following.

Theorem 2 If T approximates f with absolute accuracy δ and

δ ≤ Γ_{(τ,T)}

then the topological complexity TC(T) of T satisfies

TC(T) ≥ w(τ).
□

3 Round-off trees

A round-off tree is an algebraic computation T whose arithmetic operations are subject to some form of error. Typical examples arise when considering computations in floating-point or fixed-point arithmetic.

In what follows, we will prove lower bounds for round-off trees. We will not rely on any special kind of error. These errors can be produced by rounding or by chopping, and can satisfy bounds either for their absolute or relative magnitude. Actually, the only hypothesis for our lower bounds to hold will be the usual bound on the outcome’s accuracy and an additional hypothesis requiring that the sequence of arithmetic operation performed by the tree produces an equally accurate result. Let’s describe this more precisely.

If η is a leave of T, denote by g_{η} the polynomial computed with exact arithmetic along the path ending in η and by g̃_{η} the function computed along this path when errors are allowed.

Definition 3 Let T be a round-off tree with input space IR^{n} and output space IR, and let f : IR^{n} → IR be a function.

We say that T approximates f with absolute accuracy δ if for every input x ∈ IR^{n} the output T (x) of T satisfies 1) |T (x) − f(x)| ≤ δ, and

2) If the round-off computation of T with input x leads to the leave η then |g̃_{η}(x) − g_{η}(x)| ≤ δ.

Similarly, we say that T approximates f with relative accuracy δ upon replacing δ by δ|f(x)| in the two conditions above.

Remark 4 Notice that the adjectives “absolute” and “relative” can apply to both the errors occuring along the computation (round-off errors) and the accuracy of its outcome. However, there is no need to bound in the same way the accuracy and the round-off errors and one finds instances of algorithms with combinations of different kinds. For instance, algorithms in numerical linear algebra, say for linear equation solving, usualy consider both relative round-off errors and relative accuracy (see [Demmel 1997]); relative round-off errors are actually common in numerical analysis since they correspond to floating-point arithmetic. The main result of [Cucker and Smale 1997] considers absolute round-off errors but infinite accuracy in the answer (the problem considered there, being decisional, does not allow for approximate answers). Also, for some results on integration (cf. [Koiran 1995]), absolute accuracy is considered for exact algorithms. The list of combinations may continue but we will stop here.

A version of Theorem 1 for round-off trees follows.

Theorem 3 Let T be a round-off tree with depth k. If T approximates a piecewise polynomial function f with absolute accuracy δ and

δ ≤ \frac{Γ_{τ}}{2}

then k ≥ log_{2} w(τ).

Proof. One proceeds as in the proof of Theorem 1 to show that if k < log_{2}(w(τ) then there is a point x ∈ IR^{n} whose computation ends in a leave η of T satisfying

|f(x) − g_{η}(x)| > Γ_{τ} .

But since T δ-approximates f we have

|f(x) − T (x)| ≤ δ ≤ \frac{Γ_{τ}}{2}  and  |T (x) − g_{η}(x)| ≤ δ ≤ \frac{Γ_{τ}}{2}

the latter since T (x) = g̃_{η}(x). Therefore |f(x)−g_{η}(x)| ≤ Γ_{τ} which is a contradiction.

□

4 Extensions

Theorem 1 can be extended to some contexts where trees are endowed with additional capabilities. In this section we briefly discuss how this is carried out for two such capabilities: randomization and parallelism. We will state our results only for exact approximation trees. The result for round-off trees holds as well in the case of randomized trees but we do not know how to prove it for parallel trees.

4.1 Randomized Trees

One can define randomized versions of approximation trees by allowing “coin tossing” and requiring the output to be a δ-approximation with high probability. More precisely, we consider trees with input space IR^{n} × {0, 1}^{m} (for the arguments which follow the exact value of m is not important) and we fix a confidence degree σ satisfying 0 < σ ≤ 1. Then, such a tree approximates f with absolute accuracy δ when, for each x ∈ IR^{n} and for at least σ2^{m} points b in {0, 1}^{m}, we have |T (x, b)−f(x)| ≤ δ.

Assume that this happens and let X be the union of the grids \overline{S} associated to the sets V_{i} with i ∈ I_{τ}. Then there exists a point b^{∗} ∈ {0, 1}^{m} such that for at least σ|X| points in X we have |T (x, b) − f(x)| ≤ δ. Fix the coin tossing b^{∗} and call these points good (with respect to b^{∗}).

Lemma 2 At least \frac{σ}{2−σ} w(τ) sets V_{i} contain more than \frac{σ}{2} N_{τ}^{n} good points.

Proof. Let α be the number of sets V_{i} containing more than \frac{σ}{2} N_{τ}^{n} good points. Then

|good points| ≤ αN_{τ}^{n} + (w(τ) − α)N_{τ}^{n} \frac{σ}{2}

and since the number of good points is at least σN_{τ}^{n}w(τ) the result follows. □

To replicate the proof of Theorem 1 we now consider the deterministic tree resulting from replacing the coin tossing by the fixed point b^{∗} and we modify the quantities appearing in the definition of Γ_{τ} to allow for the confidence σ. Thus, we define I_{(τ,σ)} to be the subset of I_{τ} with those indices i such that V_{i} satisfies Lemma 2. Then, one defines d_{(τ,σ)}, C_{(τ,σ)}, D_{(τ,σ)}, N_{(τ,σ)} and Γ_{(τ,σ)} as in Section 1.

Notice that d_{(τ,σ)} ≤ d_{τ}, C_{(τ,σ)} ≥ C_{τ}, etc. and so Γ_{(τ,σ)} ≥ Γ_{τ}.

Theorem 4 If T is a randomized tree which approximates f with absolute accuracy δ and confidence σ, and

δ ≤ Γ_{(τ,σ)}

then the depth k of T satisfies

k ≥ log_{2} (\frac{σ}{2} w(τ)) .

Sketch of proof. We say that a leaf η is attached to V_{i} if η is reached by at least N_{(τ,σ)}^{n}/w(τ) good points in \overline{S}.

Again, we claim that a leaf can not be attached to two different sets V_{i} and from this claim it follows the theorem. Indeed, if

k < log_{2} (\frac{σ}{2} w(τ))

then |Leaves(T)| < σw(τ)/2 and, by the pigeonhole principle, there is a leaf of T attached to V_{i}. So, every V_{i} has a leaf attached to it. And, by hypothesis, each leaf of T is attached to at most one V_{i}. But then

|Leaves(T)| ≥ \frac{σ}{2 − σ} w(τ) ≥ \frac{σ}{2} w(τ)

and therefore, k ≥ log_{2}(\frac{σ}{2} w(τ)).

The claim is proved as in Theorem 1. □

Remark 5 When dealing with decision problems, the confidence degree σ is assumed to be greater than 1/2 (or in other words, the probability error ε = 1 − σ is assumed to be smaller than 1/2). This is due to the fact that an algorithm consisting of tossing a coin and answering Yes or No according to the outcome of that coin tossing (and independently of the input) is already a probabilistic algorithm of confidence 1/2. Theorem 4 shows that such a simple algorithm is not going to work in the non-decisional case.

We also mention that a complexity lower bound for a probabilistic tree deciding an arrangement of hyperplanes or a polyhedron was obtained in [Grigoriev 1998]. This bound is logarithmic in the number of faces.

4.2 Parallel Trees

Parallel computations can be modelled by a particular kind of trees. If p denotes the number of processors, at each computational node, the tree performs an arithmetic operation and stores its result in at most p coordinates of the state space. Also, at each branching node, the sign of at most p such coordinates is tested, giving thus rise to 2^{p} possible outcomes. An elementary computation yields an upper bound of 2^{pk} leaves for such a tree with depth k. Since in most parallel models the number of processors is bounded by 2^{k} this upper bound becomes 2^{k2^{k}}.

If the computations are performed exactly (without errors) it turns out that most of these leaves are irrelevant in the sense that there are no points in IR^{n} reaching them. More precisely, Yao [1981] (see also [Montaña and Pardo 1993]) shows that in this case, the number of leaves which are reached by points in IR^{n} is bounded by

2^{O(k^{2}n)}.

Notice that from this it follows the inequality

k ≥ Ω (\sqrt{\frac{log |Leaves(T)|}{n}}) .

We remark that an upper bound close to the latter lower one (for small dimensions) for the parallel complexity of deciding an arrangement of hyperplanes or a polyhedron (as in Remark 5) was given in [Grigoriev 1997].

An almost verbatim repetition of the proof of Theorem 1 yields the following which, we recall, we can only prove for exact trees.

Theorem 5 If T is a parallel tree which approximates f with absolute accuracy δ and

δ ≤ Γ_{τ}

then the depth k of T satisfies

k ≥ Ω (\sqrt{\frac{log_{2} w(τ)}{n}}) .

□

Remark 6 The requirement of exact arithmetic for T in Theorem 5 seems unavoidable if we want to use Yao’s bound on the number of relevant leaves. To see why, consider a set of s lines in IR^{2} given by linear polynomials ℓ_{1}, …, ℓ_{s} and assume that these lines pass through a common point ξ. Now consider a branch node which tests the signs of ℓ_{1}, …, ℓ_{s} at a point x. If x = ξ and round-off errors are allowed when computing ℓ_{i}(ξ), i = 1, …, s, we may get up to 2^{s} possible outcomes.

References

Blum, L., F. Cucker, M. Shub, and S. Smale (1998). Complexity and Real Compu-

tation. Springer-Verlag. Bürgisser, P., M. Clausen, and A. Shokrollahi (1996). Algebraic Complexity The-

ory. Springer-Verlag. Cucker, F. and S. Smale (1997). Complexity estimates depending on condition and

round-off error. To appear in Journal of the ACM. Demmel, J. (1997). Applied Numerical Linear Algebra. SIAM. Grigoriev, D. (1997). Nearly sharp complexity bounds for multiprocessor algebraic

computations. Journal of Complexity 13, 50–64. Grigoriev, D. (1998). Randomized complexity lower bounds. In 30th annual ACM

Symp. on the Theory of Computing, pp. 219–223.

Grigoriev, D., M. Karpinski, and A. Yao (1998). An exponential lower bound on the size of algebraic decision trees for MAX problem. To appear in Computational Complexity.

Koiran, P. (1995). Approximating the volume of definable sets. In 36th annual IEEE

Symp. on Foundations of Computer Science, pp. 134–141. Montaña, J. and L. Pardo (1993). Lower bounds for arithmetic networks. Applicable

Algebra in Engineering, Communication and Computing 4, 1–24. Renegar, J. (1987). On the worst case arithmetic complexity of approximating zeros of

polynomials. Journal of Complexity 3, 90–113. Smale, S. (1987). On the topology of algorithms I. Journal of Complexity 3, 81–89. Strassen, V. (1983). The computational complexity of continued fractions. SIAM Jour-

nal on Computing 12, 1–27. Vassiliev, V. (1992). Complements of Discriminants of Smooth Maps: Topology and

Applications, Volume 98 of Translations of Mathemathical Monographs. American Mathematical Society.

Yao, A. (1981). On the parallel computation of the knapsack problem. In 13th annual ACM Symp. on the Theory of Computing, pp. 123–127.