A Lower Bound for Randomized Algebraic Decision Trees

Dima Grigoriev^{∗}  Marek Karpinski^{†}  Friedhelm Meyer auf der Heide ^{‡}

Roman Smolensky ^{§}

Abstract

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces. As an application, among other things, we derive, for the first time, an Ω(n^{2}) randomized lower bound for the Knapsack Problem which was previously only known for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary technique for deterministic algebraic decision trees without making use of Milnor’s bound on Betti number of algebraic varieties.

1 Introduction

Starting with [MT82], [S83], [M85a] and [M85b] there has been a continued effort in the last decade to understand an intrinsic power of randomization in algebraic decision trees (see also [BKL93], [GK93], [GK94] for some more recent results). Several algebraic and topological methods which were introduced in proving lower bounds for deterministic algebraic decision trees (cf. [SY82], [B83], [BLY92], [GKV95], [Y94]), with the exception of [BKL93], and [GK93], were not yielding lower bounds for the case of randomized decision trees. In [M85a] a lower bound has been stated on the depth or randomized linear decision trees (randomized algebraic decision trees of degree 1) for the case of languages being finte unions of hyperplanes (a gap in the proof of the Main Lemma of [M85a] for the generic case was closed in [GK94]). Our paper provides the first lower bounds on the depth of randomized algebraic decision trees in the case of the languages being finite unions of hyperplanes as well as intersections of halfspaces. In this case we provide a new method for proving lower bounds also for deterministic algebraic decision trees without making use of Milnor’s bound and Betti numbers of algebraic varieties. As an application we derive randomized lower bounds for a number of concrete problems, among others, Knapsack (Ω(n^{2}) lower bound), and the Element Distinctness (Ω(n log n) lower bound).

∗Dept. of Computer Science and Mathematics, Penn State University, University Park. Email:

dima@cse.psu.edu

†Dept. of Computer Science, University of Bonn, 53117 Bonn. Email: marek@cs.uni-bonn.de

‡Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn.

Email: fmadh@uni-paderborn.de

§Dept. of Computer Science, University of Bonn, 53117 Bonn. Roman Smolensky has died on 19 October, 1995 in New York. This paper is also dedicated to the memory of Roman by the other co-authors. Email:

roman@cs.uni-bonn.de

The paper is organized as follows. Section 2 introduces the notation of randomized algebraic decision and computation trees. Section 3 overviews the known results in the area. Section 4 summarizes our results and applies them for the number of concrete problems. Section 5 gives an outline of the lower bound proof, and Sections 6–7 gives the proof of the Main Theorem.

2 Deterministic and Randomized Decision Trees.

An algebraic decision tree of degree d, a d-DT for inputs (x_{1}, …, x_{n}) ∈ IR^{n} is a rooted ternary tree. Its root and inner nodes are labelled by polynomials from IR[X_{1}, …, X_{n}] of degree at most d, its leaves are accepting or rejecting. The computation of the d-DT on input (x_{1}, …, x_{n}) ∈ IR^{n} consists of traversing the tree from the root to a leaf, always choosing the left/middle/right branch of a node labelled with polynomial g dependent on whether g(x_{1}, …, x_{n}) is smaller/equal/greater than 0.

The inputs (x_{1}, …, x_{n}) ∈ IR^{n} arriving at accepting leaves form the set S ⊆ IR^{n} recognized by the d-DT.

A randomized algebraic decision tree of degree d, a d-RDT, is a finite collection of d-DT s T_{α}. Such a d-RDT recognizes S ⊆ IR^{n}, if, for each x ∈ IR^{n}, at least a fraction of 1 − γ of the T_{α}’s classify x correctly w. r. t. S, for some γ ∈ (0, \frac{1}{2}), called the error probability.

The depth of T is the maximum depth of the T_{α}’s. In case of d = 1 we talk about deterministic or randomized linear decision trees, LDT s or RLDT s. In case we do not restrict the degree of the polynomials but charge for each arithmetic operation needed to compute them we talk about deterministic and randomized algebraic computation trees, CT s and RCT s (for details see [B83]) with the similar notations for depth (or time).

Note that neither the choice of the error probability from (0, \frac{1}{2}), nor the complexity measure “maximum depth” are significant. Choosing any constant error probability smaller than \frac{1}{2} and replacing maximum depth by maximum over all expected path lengths, maximum taken over all inputs (“worst case expected time”), only changes the complexity of a set S by a constant factor, see e. g. [M85c]. Also, we note here without a proof that the restriction that an RDT consists of a finite collection of DT s can be weakened: α ∈ IN, e. g., works as well.

3 Known Results.

The most important results in connection to this research are the variants of the component counting lower bound for deterministic computations: Let L ⊆ IR^{n} have q connected components. Then each LDT for L has depth Ω(log(q)) [DL75], each d-DT for L has depth Ω(\frac{log(q)}{log(d)} − n) (can be deduced from [B83]), each CT for L has depth Ω(log(q) − n) [B83].

The last two results heavily depend on Milnor’s bound on Betti numbers for real algebraic varieties, thus use deep results from algebraic topology.

In order to apply the component counting lower bound one has to count the number of connected components of interesting languages.

Consider, e. g., the Integer Programming Language L_{n,k} = {x ∈ IR^{n}, ∃a ∈ {0, …, k}^{n} : xa = 1} [M85a, M85b]. For each k ≥ 1, the family {L_{n,k}, n ∈ IN}, restricted to integer inputs, is NP -complete, for k = 1 this is the famous Knapsack Problem.

As shown in [DL78] for k = 1 and in [M85b] for arbitrary k, IR^{n} − L_{n,k} has (k + 1)^{Ω(n^{2})} many connected components, yielding lower bounds Ω(n^{2} log(k + 1)) in the above models. In [M84] it is shown that all these NP -complete problems have polynomial depth LDT s, for their ndimensional restrictions.

A further important example was the Element Distinctness Problem, with the connected components bound n!, and therefor lower bound Ω(n log n).

As far as randomized DT s are concerned much less is known. In [M85a] it is shown that deterministic and randomized LDT s, d-DT s, and CT s, resp., are polynomially related. A randomized lower bound is shown in [M85b] that extends the lower bounds for e. g. the problems mentioned above to randomized LDT s. (A gap in that proof for the generic case was closed in [GK95].)

In [BKL93] it is shown that there are benefits if randomization is used in CT s: Consider the language {(x, y) ∈ IR^{2n} : y is permutation of x} ⊆ IR^{2n}. As this language consists of n! n-dimensional linear subspaces of IR^{2n}, a restriction to an n-dimensional affine subspace in general position turns it into a set of n! isolated points. Thus its deterministic complexity is Ω(n log n) on the above deterministic models. On the other hand, as noted in [BKL93], RCT s need time O(n) only.

4 New Results.

Consider S = ⋃_{i=1}^{m} H_{i} or S^{+} = ⋂_{i=1}^{m} H_{i}^{+}, where the H_{i}’s are hyperplanes, and the H_{i}^{+}’s are halfspaces. S is often called a linear arrangement, S^{+} is a polyhedron. A k-face L of S is a k-dimensional subspace defined by intersecting n − k of the H_{i}’s. If L is k-dimensional on the boundary of S^{+}, it is also a k-face of S^{+}. We prove the following lower bound.

Main Theorem: Let H_{1}, …, H_{m} be hyperplanes in IR^{n}, S = ⋃_{i=1}^{m} H_{i}, S^{+} = ⋂_{i=1}^{m} H_{i}^{+}. If S or S^{+} has m^{Ω(n−k)} k-faces and m = (n − k)^{Ω(n−k)} for some k ∈ {1, …, n}, then each d-RDT for S or S^{+} has depth Ω((n − k) log(m)), even if d = m^{δ} for sufficiently small δ > 0.

Thus, in order to get lower bounds, we need S or S^{+} to have m^{Ω(n)} k-faces for some k. This is true e. g. for all problems mentioned in “previous results”, thus all deterministic results mentioned there can be turned into randomized ones, in particular, we get the Ω(n^{2}) lower bound for the knapsack problem for d-RDT s, even if d = m^{δ} for sufficiently small δ > 0.

Main Theorem yields directly the following concrete applications:

Main Corollary Fix degree d = m^{δ} for certain small δ > 0. Then:

(a) Lower bound for the depth of a d-RDT recognizing the Knapsack Problem is Ω(n^{2}).

(b) Lower bound for the depth of a d-RDT recognizing Element Distinctness Problem is Ω(n log n).

We note also an interesting application of our method towards the finite set {(x, y) ∈ IR^{2n} : y is a permutation of x} ⊆ IR^{2n} with the deterministic complexity Ω(n log n), and with RCT s complexity O(n) [BKL93]. Our method applies also for this set yielding Ω(n log n) lower bound for d-RDT s.

5 Outline of the Lower Bound Proof

Fix affinely independent hyperplanes H_{i} = {x ∈ IR^{n}, a_{i}x = b_{i}} for i = 1, …, n. Let v ∈ IR^{n} be such that ⋂_{i=1}^{n} H_{i} = {v}.

Let A denote the n × n-matrix whose rows are a_{1}, …, a_{n}. For a polynomial f ∈ IR[X_{1}, …, X_{n}] we consider its expansion with origin v and coordinates a_{1}, …, a_{n}; f^{(v;H_{1},...,H_{n})} (Y_{1}, …, Y_{n}) := f(v + A(Y_{1}, …, Y_{n})). Denote for brevity g = f^{(v;H_{1},...,H_{n})} and define the leading term lm(g) as follows: First take the terms of g with the least degree in Y_{n}, then among them with the least degree in Y_{n−1} and so on, till Y_{1}. One could describe lm(g) by means of infinitesimals (cf., e. g., [GV88]).

Namely for a real closed field F (see e. g. [L65]) we say that an element ε transcendental over F is an infinitesimal (with respect to F) if 0 < ε < a for any element 0 < a ∈ F. This uniquely induces the order on the field F (ε) of rational functions and further on the real closure F̃(ε) (see [L65]). Now let ε_{1} > … > ε_{n} > 0 be the elements such that ε_{ℓ+1} is infinitesimal with respect to the real closed field { \atop IR(ε)} for ε = (ε_{1}, …, ε_{ℓ}), 0 ≤ ℓ < n. Then the sign sgn(g(ε_{1}, …, ε_{n})) = sgn(lm(g)(ε_{1}, …, ε_{n})) and this property uniquely determines the term lm(g). Actually, one could stick in the arguing below with the real numbers 1 = ε_{0}^{(0)} > ε_{1}^{(0)} > … > ε_{n}^{(0)} > 0 instead of ε_{1}, …, ε_{n} where ε_{ℓ+1}^{(0)} is “considerably smaller” than ε_{ℓ}^{(0)}, 0 ≤ l ≤ n − 1. But then one should specify, what does it mean “considerably smaller”, and it is more convenient to use infinitesimals.

Now fix a family of polynomials f_{1}, …, f_{s} ∈ IR[X_{1}, …, x_{n}]. By Var^{(v,H_{1},...,H_{n})}(f_{1}, …, f_{s}) we denote the number of variables among Y_{1}, …, Y_{n} appearing in the leading terms lm(f_{1}^{(v,H_{1},...,H_{n})}), …, lm(f_{s}^{(v,H_{1},...,H_{n})}). For a d-DT T, Var^{(v;H_{1},...,H_{n})}(T) denotes the maximum of all Var^{(v;H_{1},...,H_{n})} (f_{1}, …, f_{s}), maximum taken over all f_{1}, …, f_{s} appearing as testing polynomials on a path in T. We extend the above definition to the case of less hyperplanes H_{1}, …, H_{n−k} for some 1 ≤ k ≤ n − 1. Then L = ⋂_{i=1}^{n−k} H_{i} is a k-dimensional affine subspace of IR^{n}. For an arbitrary v ∈ L we take an (n − k)-dimensional subspace U orthogonal to L, with {v} = L ∩ U. We define Var_{k}^{(v;H_{1},...,H_{n−k})} (T) as above, for the polynomials f_{1}, …, f_{s} restricted to U. The following two lemmas imply the lower bound from our Main Theorem. The following chapters contain their proofs.

Lemma 1 Let T be a d-RDT (or an RCT) recognizing L = ∪_{i=1}^{n−k}H_{i} or L^{+} = ∩_{i=1}^{n−k}H_{i}^{+} with error probability γ < \frac{1}{2}. Then V ar^{(v;H_{1},...,H_{n−k})}(T_{α}) ≥ (1 − 2γ)^{2} · (n − k) for a fraction of \frac{1−2γ}{2−2γ} of all T_{α}’s.

Let us denote IR_{+}^{n} = {(x_{1}, …, x_{n}) : x_{i} ≥ 0, 1 ≤ i ≤ n} and IR_{0}^{n} = (IR \ {0})^{n}. Lemma 1 entails two direct corollaries for both RDT s and RCT s, which give an interesting geometric interpretation of the depth bounds of Lemma 1.

Corollary 1. Any RCT which recognizes IR_{+}^{n} or IR_{0}^{n} must have the depth greater than or equal to \frac{1}{2}(1 − 2γ)^{2}n.

Corollary 2. Any d-RDT which recognizes IR_{+}^{n} or IR_{0}^{n} must have the depth greater or equal to \frac{1}{d}(1 − 2γ)^{2}n.

Let T′ be an d-DT, and S = ∪_{i=1}^{m}H_{i} or S = ∩_{i=1}^{m}H_{i}^{+} for hyperplanes H_{1}, …, H_{m} ∈ IR^{n}.

For a k-face L of S let 1 ≤ i_{1} < … < i_{n−k} ≤ m be the lexicographically smallest sequence of (n− k) indices such that L = H_{i_{1}} ∩…∩H_{i_{n−k}}. Let v_{L} belong to L but to no lower-dimensional face of S or S^{+}. We abbreviate Var_{k}^{(v_{L},H_{i_{1}},...,H_{i_{n−k}})}(T′) by Var^{(v_{L})}(T′).

Lemma 2 Assume that, for some c > 0, there are at least M k-faces L of S with V ar_{k}^{(v_{L})}(T′) ≥ c(n − k). Then the depth t of T′ fulfils M ≤ 3^{t} · m^{(1−c)(n−k)} · (td)^{c(n−k)}.

Using these lemmas it is easy to conclude the Main Theorem: Consider d-RDT for S or S^{+} with error probability γ < \frac{1}{2}. S, S^{+} have N many k-faces. Lemma 1 and elementary counting implies that there is α such that T_{α} fulfils: Var_{k}^{{v_{L}}} (T_{α}) ≥ (1 − 2γ)^{2}(n − k) for (\frac{1−2γ}{2−2γ}) · N many k-faces L.

Thus Lemma 2 implies the desired Ω((n − k) log(m)) lower bound, if N is large as demanded in the Main Theorem.

6 Proof of Lemma 1

First observe that it is sufficient to prove the lemma for k = 0 and under the assumption that v = 0 and the H_{i}’s are defined by {x ∈ IR^{n}, x_{i} = 0}, in other words the expansion (y_{1}, …, y_{n}) ⊢ v + A(y_{1}, …, y_{n}) is the identity.

Now let the d-RDT (or the RCT) recognize ⋂_{i=1}^{n} H_{i}^{+} with error probability γ < \frac{1}{2}.

Consider the points E = (ε_{1}, …, ε_{n}) and E_{i}^{(+)} = (ε_{1}, …, ε_{i−1}, −ε_{i}, ε_{i+1}, …, ε_{n}), i = 1, …, n. Easy counting yields that there is a fraction of (1 − 2γ)/(2 − 2γ) of the T_{α}’s that classify E and at least (1 − 2γ)^{2}n many E_{i}’s correctly. Take one such T_{α} and some i_{o} such that T_{α} classifies E_{i_{o}}^{+} correctly.

Denote by f_{1}, …, f_{s} the testing polynomials along the path in T_{α} followed by input E. We claim that X_{i_{0}} occurs in one of the leading terms lm(f_{1}), …, lm(f_{s}). Indeed, otherwise sgn(f_{ℓ}(E_{i_{0}}^{(+)})) = sgn(lm(f_{ℓ}(E_{i_{0}}^{(+)}))) = sgn(lm(f_{ℓ}(E))) = sgn(f_{ℓ}(E)), 1 ≤ ℓ ≤ s, therefore E_{i_{0}}^{(+)} satisfies all the tests along the same path as E, hence the output for E_{i_{0}}^{(+)} would be “yes”, which contradicts to the choice of i_{0}. This implies Lemma 1 for ⋂_{i=1}^{n} H_{i}^{+}.

In case of T recognizing ⋃_{i=1}^{n} H_{i} consider the points E_{i}^{(0)} = (ε_{1}, …, ε_{i−1}, 0, ε_{i+1}, …, ε_{n}), 1 ≤ i ≤ n and argue as above, replacing E_{i}^{(+)} by E_{i}^{(0)}, 1 ≤ i ≤ n.

7 Proof of Lemma 2

To every k-face L defined by an intersection H_{i_{1}} ⋂ … ⋂ H_{i_{n−k}}, i_{1} < … < i_{n−k}, see above, with Var^{(v_{L})}(T′) ≥ c(n − k), we correspond a path in T′ with the testing polynomials f_{1}, …, f_{s} for which Var^{(v_{L})}(T′) = Var^{(v_{L})}(f_{1}, …, f_{s}).

By a flag of L we mean the sequence of embedded planes

H_{i_{n−k}}  ⊃  H_{i_{n−k}} ⋂ H_{i_{n−k−1}}  ⊃
H_{i_{n−k}} ⋂ H_{i_{n−k−1}} ⋂ H_{i_{n−k−2}}  ⊃  …  ⊃

⋂ H_{i_{n−k}} ⋂ … ⋂ H_{i_{1}}

where i_{1} < … < i_{n−k} were yielded above. Our purpose is to label some of these planes in an appropriate way. As a result , a labeled flag would be attached to L. Morever, for a fixed path in T′ with the testing polynomials f_{1}, …, f_{s} we organize the labeled flags attached to all k-faces L which correspond to this path as a regular tree T = T (f_{1}, …, f_{s}) with all the paths of the same length n − k.

We construct the tree T and thereby the labeled flags by induction on the level . The base of induction. Take L which corresponds to the fixed path (we utilize the introduced above notations for the coordinates in a neighbourhood of v_{L}). If Y_{n−k} (or in other words, hyperplane H_{i_{n−k}}) divides one of f_{1}, …, f_{s} we construct a vertex, being a son of the root of the tree T , mark it with the hyperplane H_{i_{n−k}} and label. If Y_{n−k} does not divide any of f_{1}, …, f_{s}, we do not label this vertex of T . To complete the construction of the first level of T , we represent the polynomial f_{j} = f̃_{j}Y_{n−k}^{m_{j}}L_{H_{r_{1}}}^{m_{j,1}} … L_{H_{rp}}^{m_{j,p}}, 1 ≤ j ≤ s as a product for maximal possible m_{j}, m_{j,1}, …, m_{j,p} where i_{n−k} < r_{1} < … < r_{p} and L_{H_{r_{1}}} , …, L_{H_{rp}} are all linear polynomials determining hyperplanes H_{r_{1}}, …, H_{r_{p}} which divide f_{j} with the indices r_{1}, …, r_{p} greater than i_{n−k}. We assign to the constructed vertex the polynomials f_{j}^{(1)}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}) = f̃_{j}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}, 0), 1 ≤ j ≤ s. One could view the polynomial f_{j}^{(1)} as being defined on the hyperplane H_{i_{n−k}}.

Observe that the linear polynomials L_{H_{r_{1}}} … L_{H_{rp}} do not vanish on L (due to the choice of i_{n−k}) and therefore these linear polynomials do not vanish at v_{L}, hence the expansion in the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} of L_{H_{r_{l}}}, 1 ≤ l ≤ p contains nonzero constant term which is thereby its leading term, thus lm^{(v_{L})}(f_{j}) coincides with lm^{(v_{L})}(f̃_{j}Y_{n−k}^{m_{j}}) up to a constant factor. Furthermore, lm^{(v_{L})}(f̃_{j}Y_{n−k}^{m_{j}}) = lm^{(v_{L})}(f̃_{j})Y_{n−k}^{m_{j}} = lm^{(v_{L})}(f_{j}^{(1)})Y_{n−k}^{m_{j}},1 ≤ j ≤ s, and so the leading term of the new polynomial f_{j}^{(1)} up to a constant factor is obtained from the leading term of the former polynomial f_{j} by dividing on Y_{n−k}^{m_{j}}, 1 ≤ j ≤ s. We refer to this property as the maintenance of the leading term. In particular, if the vertex of T under consideration is not labeled, the leading term of all the polynomials change only up to constant factors. If Y_{n−k} occurs in one of lm^{(v_{L})}(f_{j}), 1 ≤ j ≤ s then the vertex is labeled.

Notice that all the k-faces with the same first hyperplane H_{i_{n−k}} in their flags, correspond to the constructed vertex ( marked with H_{i_{n−k}}). Remark that the polynomials f_{j}^{(1)}, 1 ≤ j ≤ s do not depend on a particular k-face, but still we expand them in the coordinates which depend on L (so, v_{L}).

Now suppose by induction that ℓ < n levels of the tree T are already constructed. Consider any vertex w of T at ℓ-th level. To the vertex w leads to path (partially labeled), whose vertices are marked successively by the beginning elements of a flag

H_{i_{n−k}} ⊃ H_{i_{n−k}} ⋂ H_{i_{n−k−1}} ⊃ … ⊃ H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−ℓ+1}}.

Finally, the polynomials f_{j}^{(ℓ)}, 1 ≤ j ≤ s are assigned to the vertex w. One could look at f_{j}^{(ℓ)}, 1 ≤ j ≤ s as a polynomial restricted on (n − ℓ)-dimension plane H = H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−ℓ+1}}.

If this is the beginning of the flag of a k-face L (we still consider L to keep the notations), then we can regard f_{j}^{(ℓ)} (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−ℓ}) , 1 ≤ j ≤ s as the polynomials in the fixed coordinates in the neighbourhood of v_{L}. As above we construct a new vertex of T of the level (ℓ + 1), being a son in T of the vertex under consideration, and mark it with the (n − ℓ − 1)-dimensional plane H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−ℓ+1}} ⋂ H_{i_{n−k−ℓ}} = H ⋂ H_{i_{n−k−ℓ}}.

Represent  f_{j}^{(ℓ)}  =

f̃_{j}^{(ℓ)}Y_{n−k−ℓ}^{q_{j}}L_{H ⋂ H_{t_{1}}}^{q_{j,1}} … L_{H ⋂ H_{tπ}}^{q_{j,π}} , 1 ≤ j ≤ s for the maximal possible q_{j}, q_{j,1}, …, q_{j,π} where i_{n−k−ℓ} < t_{1} < … < t_{π} and L_{H ⋂ H_{t_{1}}} , …, L_{H ⋂ H_{tπ}} are all the linear polynomials in the plane H determining hyperplanes H ⋂ H_{t_{1}}, …, H ⋂ H_{t_{π}} (in H) which divide f_{j}^{(ℓ)} with the indices t_{1}, …, t_{π} greater than i_{n−k−ℓ}. We assign to the constructed vertex the polynomials f_{j}^{(ℓ+1)} =

f̃_{j}^{(ℓ)} (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−ℓ−1}, 0) , 1 ≤ j ≤ s.

One could view the polynomial f_{j}^{(ℓ+1)} as being defined on the plane H ⋂ H_{i_{n−k−ℓ}}.

If q_{j} ≥ 1 for at least one 1 ≤ j ≤ s then we label the constructed vertex. As in the base of the induction we observe that the linear polynomials L_{H ⋂ H_{t_{1}}} , …, L_{H ⋂ H_{tπ}} do not vanish on L (due to the choice of i_{n−k−l}) and therefore these linear polynomials do not vanish at v_{L}, hence the expansion in the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l} of L_{H ⋂ H_{t_{θ}}}, 1 ≤ θ ≤ π contains nonzero constant term which is thereby its leading term (with respect to the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−ℓ}). Thus, lm^{(v_{L})}f_{j}^{(ℓ)} coincides with lm^{(v_{L})} (f̃_{j}^{(l)}Y_{n−k−l}^{q_{j}}) up to a constant factor. Furthermore,

lm^{(v_{L})} (f̃_{j}^{(ℓ)}Y_{n−k−ℓ}^{q_{j}}) = lm^{(v_{L})} \binom{}{f̃_{j}^{(ℓ)}} · Y_{n−k−ℓ}^{q_{j}} =

lm^{(v_{L})} (f_{j}^{(ℓ+1)}) Y_{n−k−ℓ}^{q_{j}}, 1 ≤ j ≤ s. So, the lead-

ing term of the new polynomial f_{j}^{(ℓ+1)} up to a constant factor is obtained from the leading term of the former polynomial f_{j}^{(ℓ)} by dividing on Y_{n−k−ℓ}^{q_{j}}, 1 ≤ j ≤ s. Thus, we have ascertained the maintenance property of the leading terms (see the base of induction). Also the vertex is labeled if and only if Y_{n−k−ℓ} occurs in one of lm^{(v_{L})} (f_{j}^{(ℓ)}) , 1 ≤ j ≤ s.

This completes the inductive construction of T . Observe that to each path in T corresponds exactly one k-face represented by a flag marked on the path. Vice versa, by the construction of T every k-face L which corresponds to the fixed path of d - DT T′ with the testing polynomials f_{1}, …, f_{s}, appears in some leaf of T .

Now let us estimate the number of leaves in T . By the assumption of the lemma and due to the property of the maintenance of the leading terms on each path of T at least c(n − k) vertices are labeled. Observe that in the inductive step of the described construction of T the constructed vertex (being a son of the vertex w of the level ℓ; we utilize the introduced above notations) which corresponds to the hyperplane H ⋂ H_{i_{n−k−ℓ}} (in H) is labeled if and only if the linear polynomial L_{H ⋂ H_{i_{n−k−ℓ}}} divides

the product ∏_{1≤j≤s} f_{j}^{(ℓ)}. Let u_{1} < … < u_{p} be all the indices such that L_{H ⋂ H_{uq}} divides the

product ∏_{1≤j≤s} f_{j}^{(ℓ)}, 1 ≤ q ≤ p. By the observed above each labeled son of the vertex w is marked with some H_{u_{q_{0}}} , 1 ≤ q_{0} ≤ p. Since in the construction of f_{j}^{(ℓ+1)}, 1 ≤ j ≤ s we divided by L_{H ⋂ H_{uq}} for all q > q_{0}, we con-

clude that the degree deg (∏_{1≤j≤s} f_{j}^{(ℓ+1)}) ≤

deg (∏_{1≤j≤s} f_{j}^{(ℓ)})−(p − q_{0} + 1). Notice that the

polynomials f_{j}^{(ℓ+1)}, 1 ≤ j ≤ s depend actually on the particular son of the vertex w, although we do not reflect this in the notations.

Besides the labeled sons, any vertex in T could have at most m unlabeled sons (in fact, each unlabeled son is marked with some H_{u} with u < i_{n−k−ℓ+1}, so there are less than m sons in general, but we stick with a rough bound m which suffices).

To estimate the number of leaves in T denote by M(R, Q, D) the maximal possible number of leaves in a regular tree (actually, we could stick with subtrees of T , so they are partially labeled) with the length of any path equal to R, with at most Q unlabeled vertices on any path and with a polynomial of degree less or equal to D assigned to any vertex (in T we assign the polynomial ∏_{1≤j≤s} f_{j}^{(ℓ)} to the vertex w, see the construction). Assume w · ℓ · o · g· that Q ≤ R (if Q > R then set M(R, Q, D) = 0). Considering such a tree and its subtrees with the roots being the sons of the root of the tree we get the following inductive inequality M(R, Q, D) ≤ m·M(R−1, Q−1, D)+∑_{1≤p≤D} M(R−1, Q, D− p) (provided that R > Q, when R = Q we have M(Q, Q, D) ≤ m · M(Q − 1, Q − 1, D) where the first item in the right side relates the unlabeled sons of the root and the second item relates the labeled sons (see the bound on deg (∏_{1≤j≤s} f_{j}^{(ℓ+1)})). ¿From this inequality we get a bound (by induction on R) :

M(R, Q, D) ≤ m^{Q} \frac{D^{R−Q}}{(R − Q)!}\binom{R}{Q}.

Indeed, the right side of the inequality by inductive hypothesis does not exceed (provided that R > Q, when R = Q we have M(Q, Q, D) ≤ m^{Q} by induction on Q)

m^{Q} \frac{D^{R−Q}}{(R − Q)!}\binom{R − 1}{Q − 1}

+ ∑_{0≤p≤D−1} m^{Q} \frac{p^{R−Q−1}}{(R − Q − 1)!}\binom{R − 1}{Q}

≤ m^{Q}(\frac{D^{R−Q}}{(R − Q)!}\binom{R − 1}{Q − 1}

+\binom{R − 1}{Q}\frac{1}{(R − Q − 1)!} \frac{D^{R−Q}}{R − Q})

= m^{Q} \frac{D^{R−Q}}{(R − Q)!}\binom{R}{Q}

which was to be shown. Substituting now

R = n − k, Q = (n − k)(1 − c),

D = deg( ∏_{1≤j≤s} f_{j}) ≤ sd,

we obtain a bound

m^{(n−k)(1−c)} \frac{(sd)^{c(n−k)}}{(c(n − k))!}2^{n−k}

≤ m^{(n−k)(1−c)}(sd)^{c(n−k)}

for the number of leaves in T .

So far, we’ve considered one path of the ddecision tree T′ (with the testing polynomials f_{1}, …, f_{s} along this path).

Denote by t the depth of T′ (thus, T′ has at most 3^{t} paths). Since each k-face corresponds to a certain path of T′ (see the beginning of the proof of the lemma), we conclude that

M ≤ 3^{t}m^{(n−k)(1−c)}(td)^{c(n−k)},

which proves Lemma 2.

8 Applications

There is a number of applications of our method for concrete problems (see for examples, e. g.,

[B83] or [M85a]). We shall discuss the full list of concrete problems for which our method applies, and the corresponding randomized lower bounds, in the final version of this paper. Here we give only in Main Corollary, Section 4, the applications for the Knapsack, and the Element Distinctness Problems with the randomized bounds Ω(n^{2}) and Ω(n log n), respectively.

9 Conclusion and Open Problems

We have proven that the known counting lower bounds for DT s carry over to RDT s for sets being finite unions of hyperplanes and intersections of halfspaces. Two important questions remain open:

• Does our lower bound for RDT s hold also for sets of other structure, e. g. finite languages?

Using the method of Example 2 in [BKL93] on polynomial zero-tests we can construct a finite set of n! points (permutations) in IR^{n}, for which an RDT with degree n (cf. also the restriction on M in Theorem 2) needs a constant time. For Randomized Computation Trees (RCT s) the above algorithm needs depth O(n) and Ben-Or’s ([B83]) lower bound Ω(n log n) holds for deterministic CT s. Our lower bound does not give nontrivial bounds for RDT s of degree m for this problem.

• Is there some analog of our Main Theorem also possible for randomized computation trees (RCT s) ?

References

[B83] M. Ben-Or, Lower Bounds for Algebraic Computation Trees, Proc. 15th ACM STOC (1983), pp. 80–86.

[BLY92] A. Björner, L. Lovasz and A. Yao, Linear Decision Trees: Volume Estimates and Topological Bounds, Proc. 24th ACM STOC (1992), pp. 170–177.

[BKL93] P. Buergisser, M. Karpinski, T. Lickteig, On Randomized Algebraic Test Complexity, J. of Complexity 9 (1993), pp. 231-251.

[DL78] D.P. Dobkin, R.J. Lipton, A Lower Bound of \frac{1}{2}n^{2} on Linear Search Programms for the Knapsack Problem, J.Compt.Syst.Sci. 16 (1978), pp. 413– 417.

[GK93] D. Grigoriev, M. Karpinski, Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees, Technical Report TR-93-042, International Computer Science Institute, Berkeley, 1993.

[GK94] D. Grigoriev, M. Karpinski, Lower Bound for Randomized Linear Decision Tree Recognizing a Union of Hyperplanes in a Generic Position , Research Report No. 85114-CS, University of Bonn, 1994.

[GKV95] D. Grigoriev, M. Karpinski, N. Vorobjov, Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Proc. 36th IEEE FOCS (1995), pp. 258-265.

[GV88] D. Grigoriev, N. Vorobjov, Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Comp. 5 (1988), pp. 37–64.

[L65] S. Lang, Algebra, Addison–Wesley, New York, 1965.

[M84] F. Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, J. ACM 31 (1984), pp. 668–676.

[M85a] F. Meyer auf der Heide, Nondeterministic versus Probabilistic Linear Search Algorithms, Proc. IEEE FOCS (1985), pp. 65–73.

[M85b] F. Meyer auf der Heide, Lower Bounds for Solving Linear Diophantic Equations on Random Access Machines, J. ACM 32 (1985), pp. 929–937.

[M85c] F. Meyer auf der Heide, Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theoretical Computer Science 41 (1985), pp. 325– 330.

[MT82] U. Manber and M. Tompa, Probabilistic, Nondeterministic and Alternating Decision Trees, Proc. 14th ACM STOC (1982), pp. 234–244.

[S83] M. Snir, Lower Bounds for Probabilistic Linear Decision Trees, Research Report 83–6, Dept. of Computer Science, Hebrew University of Jerusalem, 1983.

[SY82] J. M. Steele and A. C. Yao, Lower Bounds for Algebraic Decision Trees, J. of Algorithms 3 (1982), pp. 1–8.

[T51] A. Tarski, A Decision Method for Elementary Algebra and Geometry, University of California Press, 1951.

[Y92] A. Yao, Algebraic Decision Trees and Euler Characteristics, Proc. 33rd IEEE FOCS (1992), pp. 268–277.

[Y94] A. Yao, Decision Tree Complexity and Betti Numbers, Proc. 26th ACM STOC (1994), pp. 615–624.