An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

D. Grigoriev^{∗}  M. Karpinski^{†}  A. C. Yao^{‡}

Abstract

We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n − 1 lower bound of Rabin [R72] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on size for the polyhedral decision problem MAX= of testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraphs on n vertices.

∗Departments of Computer Science and Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802; grigorie@cse.psu.edu. The research of this author is supported in part by the National Science Foundation under grant CCR-942 4358.

†Department of Computer Science, University of Bonn, 53117 Bonn; marek@theory.cs.uni-bonn.de. Research partially done while visiting Department of Computer Science, Princeton University and DIMACS. The research of this author is supported in part by the DFG Grant KA 673/4-1, and by the ESPRIT BR Grants 7097 and EC-US 030.

‡Department of Computer Science, Princeton University, Princeton, New Jersey 08544; yao@cs.princeton.edu. The research of this author is supported in part by National Science Foundation under grant CCR-9301430.

1 Introduction

The minimum depth of decision trees has been extensively studied for many computational problems in the literature. However, another natural complexity measure, the minimum size of decision trees is much less understood. For business applications (e.g. [GS79]) and for some computational problems, the size of decision trees gives a reasonable measure of the space required to implement the corresponding algorithms. For example, consider the membership problem for a given polyhedron in n dimensions. Unless the polyhedron has a highly-structured description, it is reasonable to expect that many decision trees (especially those with optimized depth) have to be stored in order for the membership queries to be processed with an efficiency reflecting the depths of the trees.

We focus our attention to computations in IR^{n} that can be modeled by algebraic decision trees; these include many geometric and searching-sorting problems. Clearly, the size of a decision tree is no less than its depth, and thus a lower bound to the depth of all decisions trees for solving a problem is also a lower bound to the size of all such trees. Other than this obvious observation, the only lower bounds known are those for linear decision trees (where only linear functions are used for branching, see e.g., [DL75], [BLY92]), typically exponential in the depth. For higher degree algebraic decision trees, no superpolynomial lower bounds are known for natural problems, except with further constraints on the test polynomials.

In this paper we investigate the size complexity of algebraic decision trees for MAX, the problem of finding the maximum of n real numbers, which was studied extensively in the literature (cf., e.g., [K73], [R72], [TY94]). We use the standard degree-d ternary algebraic decision tree model in which each internal node performs a test p(x_{1}, x_{2}, ⋯, x_{n}) : 0 (where p is any real polynomial of degree d) with <, =, > as the possible outcomes. Rabin [R72] established the sharp lower bound n − 1 on the depth of any binary algebraic decision tree (for any d) solving this problem (see also [MPR94]). Rabin’s depth lower bound holds also for ternary algebraic decision trees. Except for linear decision trees (d = 1) and for cases with special restricted forms of polynomial tests (see Remark 1), no nonlinear lower bound was known on the size.

Let “MAX=” denote the problem of verifying x_{1} ≥ x_{k} for all 1 ≤ k ≤ n. The main result of the present paper is to show that, for any fixed d, the size of any degree-d algebraic decision tree for solving MAX= (and hence MAX) is at least 2^{c′(d)n} for some positive constant c′(d). We will also establish an interesting connection between this lower bound and the maximum number of minimal cutsets for any rank-d hypergraphs on n vertices. This connection enables us to obtain better values of c′(d). There are many interesting open problems suggested by our work, some of which are mentioned in the remarks below and at the end of Section 2.

Remark 1. A direct motivation for the present study is the close relation between the size of decision trees for MAX and the depth of decision trees for selecting the i largest elements. Let a_{d,n} be the minimum size of any degree-d algebraic decision tree for solving MAX for almost all inputs (i.e., except for a measure-0 set). Then any degree-d algebraic decision tree for selecting the i largest elements must have depth greater than log_{2}(a_{d,n}\binom{n}{i−1}). This approach to the selection problem was first formulated in [FG79] for the case d = 1. It is well known that Farkas Lemma implies a_{d,n} = 2^{n−1} for d = 1. In [Y89] and [F93], it was proved that a_{d,n} = 2^{n−1} if the test polynomials are restricted to (x_{j} − x_{k})(x_{h} − x_{s}) and products of linear forms, respectively, leading to lower bounds n + (i − 1) log_{2} n + O(1) or the selection problems under such constraints (the depth lower bounds hold for both binary and ternary algebraic decision trees).

Conjecture 1: a_{d,n} = 2^{n−1} for all d, n.

A proof of this conjecture would imply that the depth complexity of algebraic decision tree for selecting the i largest elements among n is n + (i − 1) log_{2} n + θ(1), which has been an open problem for some time. Even a proof of the conjecture for d = 2 will be of much interest.

Remark 2 All the known exponential lower bounds on decision tree size for MAX, as discussed in Remark 1, were proved with the following approach: show that every branch of the tree has to be of length n − 1 or more. This is no longer possible for the general case even for d = 2, since a degree-2 decision tree with the root node testing p = x_{1} − x_{2}^{2} − ⋯ − x_{n}^{2} − 1 : 0 has a branch of length 1 (the branch with p(x) > 0 at the root). To our knowledge, no lower bound better than n − 1 is known before this paper.

Remark 3 We consider in the paper standard ternary decision trees (cf. [SY82], [B83]) branching according to the signs >, =, <. Notice that for binary decision trees studied in [R72] (branching according to the signs ≤, >), MAX= has an (n − 1)-size linear decision tree, namely the tree which successively tests x_{1} ≥ x_{2}, x_{1} ≥ x_{3}, …, x_{1} ≥ x_{n−1}. (More generally, this construction shows that the membership problem for any polyhedron defined by k inequalities has a linear decision tree of size k + 1 in this binary tree model; compare this with the lower bound on the depth Ω(logN) of [GKV95] where N is the number of all the faces of a polyhedron). On the other hand, MAX does not seem to have any polynomial-size trees in the binary tree model.

Conjecture 2: Any binary algebraic decision tree (of any degree) for MAX must have size 2^{Ω(n)}.

It is not hard to see that Conjecture 1 implies Conjecture 2. We also mention that for the membership problem to a union of k hyperplanes ⋃_{1≤i≤k} a_{i}X = b_{i}, there is a ternary (as

well as binary) algebraic decision tree of the size k. It simply tests (a_{1}X − b_{1})^{2}, then, if the sign is >, tests (a_{2}X − b_{2})^{2}, etc. Notice that this tree is nonlinear.

Remark 4 A more refined way to model space requirement is to consider branching programs (see e.g., [BFKLT81], [BFMUW87]) in which “equivalent” nodes are permitted to be merged together. Very little is known about branching programs with algebraic decision elements (however, see [Y82]).

2 Summary of Results

Consider an input n-tuple of real numbers (x_{1}, …, x_{n}) ∈ IR^{n}. An Algebraic Decision Tree (ADT) T of degree d and dimension n for MAX (MAX=) is a ternary tree with each internal node performing a ternary test p(x_{1}, x_{2}, ⋯, x_{n}) : 0 where p is a polynomials of degree at most d, and branching according to the outcomes (<, =, or >). Each leaf of the tree is either labeled by a certain index i ∈ {1, …, n} (MAX), or by a label “yes”or “no” (MAX=). We say that the decision tree T solves MAX (MAX=) in dimension n if, for an arbitrary input vector (x_{1}, …, x_{n}) ∈ IR^{n}, the path traversed in T terminates in a leaf labeled by i (“yes”) if and only if x_{i} = max{x_{1}, …, x_{n}} (x_{1} = max{x_{1}, …, x_{n}}, respectively). The size (resp. depth) of T is the number of its leaves (resp. the maximum length of its paths). It is well-known [R72] that the depth of an ADT for MAX is at least n − 1. This bound is optimal as one can easily construct T with the depth n − 1 and size 2^{n−1}.

We prove an exponential lower bound on the size.

Theorem 1 Any algebraic decision tree of degree d solving MAX (MAX=) in dimension n has size at least Ω(2^{c′(d)n}) where c′(d) > 0 depends only on d.

A hypergraph F on vertex set {1, …, N} is a family of subsets of {1, …, N}. The rank of F is the maximum size of any member of F. A minimal cutset of F is a set V ⊆ {1, …, N} which intersects every member set of F and no proper subset of V has this property. Let us denote by m_{F} the number of minimal cutsets of F. Let m_{d,N} be the maximum m_{F} for any hypergraphs F of rank d or less on N vertices. For d = 2, a hypergraph becomes a graph, and m_{2,N} is equal to the maximum number of maximal cliques of any N-vertex graph, which by a result of Moon and Moser [MM65] is equal to θ(3^{N/3}).

A slight variation of the proof of Theorem 1 leads to an interesting connection of our lower bound to the combinatorial quantity m_{d,N}.

Theorem 2 Any algebraic decision tree of degree d solving MAX (MAX=) in dimension n has size at least 2^{n−1}/m_{d,n−1}.

¿From the fact m_{2,N} = θ(3^{N/3}), it follows then that any degree-2 algebraic decision tree for MAX (MAX=) must have size Ω(2^{c′(d)n}) with c′(2) = 1 − (log_{2} 3)/3 ≈ 0.47. This improves over the value 1 − _{\frac{1}{1+ \frac{1}{2} log_{2}( \frac{4}{3} )}} ≈ 0.18 for c′(2) obtained in the proof of Theorem 1 (see Section 3); it also improves all the c′(d) for d > 2, since the proof of Theorem 1 defines c′(d) recursively.

Remark 5 An interesting open combinatorial question is to determine as small as possible function λ(d) for which m_{d,N} ≤ O(2^{λ(d)N}). By Theorem 2, we can then choose c′(d) in Theorem 1 to be 1 − λ(d). To our knowledge, even the best λ(3) has not been determined.

3 Proof of Theorem 1

Clearly every decision tree for MAX can be easily converted into a decision tree for the MAX= by relabeling a leaf “yes” whenever it is originally leabled as “x_{1} is maximum”. Thus we only need to prove Theorem 1 for MAX=.

For any {1} ⊂ I ⊂ {1, …, n} consider the following (‘wall’) set M_{I} = {(x_{1}, …, x_{n}) : x_{i} > x_{j} for all i ∈ I, j ∉ I and x_{i_{1}} = x_{i_{2}} for all i_{1}, i_{2} ∈ I}. Denote the plane P_{I} = {(x_{1}, …, x_{n}) : x_{i_{1}} = x_{i_{2}} for all i_{1}, i_{2} ∈ I}. Then dim P_{I} = n − |I| + 1 and M_{I} is an open polyhedron in P_{I}. Note that P_{{1}} = IR^{n} and all P_{I} are pairwise distinct. Obviously, the sets M_{I} are pairwise disjoint and form a partition of the set x_{1} = max{x_{1}, …, x_{n}} with 2^{n−1} elements. Observe that the Euclidian closure \overline{M_{I}} has a non-empty intersection with M_{J} if and only if I ⊂ J. Moreover, if \overline{M_{I}} ⋂ M_{J} ≠ ∅ then \overline{M_{I}} ⊃ M_{J}, and if I {⊂ \atop ≠}J then ∂M_{I} ⊃ M_{J}. Thus, {M_{I}} form a cellular decomposition of the set x_{1} = max{x_{1}, …, x_{n}} and the boundary ∂M_{I} = ⋃_{J {⊃ \atop ≠} I} M_{J} in the plane P_{I} (this property is called the frontier

condition and a corresponding decomposition is called a cellular decomposition).

The method of our proof is based on the analysis of a “touching frequency” of the sets computed along the branches of a tree T with the ‘wall sets’ M_{I}.

Consider any branch B (i.e., a path from the root to some leaf) of the tree T, and let the testing polynomials together with their signs along this branch be f_{1} = ⋯ = f_{k} = 0, g_{1} > 0, …, g_{l} > 0. Let W_{B} ⊂ IR^{n} denote the (semialgebraic) set of all x = (x_{1}, x_{2}, ⋯, x_{n}) satisfying {f_{1}(x) = ⋯ = f_{k}(x) = 0, g_{1}(x) > 0, …, g_{l}(x) > 0}. We say that W_{B} touches M_{I} if dim(W_{B} ⋂ M_{I}) = dim M_{I} = n − |I| + 1. Observe that if W_{B} touches M_{I} then the label of B is “yes”. Since for every M_{I} there exists B such that W_{B} touches M_{I}, Theorem 1 follows immediately from the Main Lemma below.

Main Lemma. For any branch B of T, W_{B} can touch at most 2^{c(d)n} sets M_{I} for some constant c(d) < 1 dependent only on d.

Define c(d) recursively as follows. Let c(1) = 0, and c(d) = c(d − 1) + \frac{(1−c(d−1))^{2}}{1−c(d−1)+ \frac{1}{d} log_{2}( \frac{2^{d}}{2^{d}−1} )} for d ≥ 2. It is straightforward to verify that 0 ≤ c(d) < 1 for all d.

We now prove the Main Lemma by a series of Propositions.

Proposition 1. W_{B} cannot touch M_{I}, M_{J} such that I {⊃ \atop ≠}J.

Proof. Assume the contrary. Let {j_{1}, …, j_{n−|J|}} = {1, …, n} \ J. For any polynomial f ∈ IR[X_{1}, …, X_{n}] denote f^{(J)}(X_{1}, X_{j_{1}}, …, X_{j_{n−|J|}}) = f|_{X_{j}=X_{1},j∈J} ∈ IR[X_{1}, X_{j_{1}}, …, X_{j_{n−|J|}}]. (From now on, we sometimes use the notation X_{i} instead of x_{i} when they are considered as formal variables instead of numbers.) One could consider f^{(J)} as the restriction of f on the plane P_{J} with the coordinates X_{1}, X_{j_{1}}, …, X_{j_{n−|J|}}, where X_{1} = X_{j} for each j ∈ J. Then f_{1}^{(J)}, …, f_{k}^{(J)} vanish identically because these polynomials vanish on the semialgebraic set W_{B} ⋂ M_{J} of full dimension in the plane P_{J}.

By assumption there exists a point x ∈ M_{I} such that g_{1}(x) > 0, …, g_{ℓ}(x) > 0. There exists a ball B_{x}(r) with a radius r > 0 centered in x such that g_{1}, …, g_{l} are positive everywhere on B_{x}(r). As x ∈ M_{I} ⊂ ∂\overline{M_{J}} there exists a point x′ ∈ (B_{x}(r) ⋂ P_{J}) \ \overline{M_{J}}. The decision tree T being applied to x′ goes through the branch B, since x′ = (x′_{1}, …, x′_{n}) ∈ W_{B}. Since branch B leads to a “yes” leave, the input x′ is accepted by the decision tree. This is a contradiction, as max(x′_{1}, …, x′_{n}) is not x′_{1} (x′ ∉ \overline{M_{J}}). □

Remark 6. In fact we proved a stronger statement. Namely, if W_{B} touches M_{J} then W_{B} ⋂ M_{I} = ∅ for any I {⊃ \atop ≠}J.

Proposition 2. If W_{B} touches M_{I} then I is a minimal subset (with respect to the inclusion) among the subsets {1} ⊂ J ⊂ {1, …, n} such that f_{1}^{(J)}, …, f_{k}^{(J)} vanish identically.

Proof. Firstly, as we have seen in the proof of Proposition 1, f_{1}^{(I)}, …, f_{k}^{(I)} vanish identically since W_{B} touches M_{I}. Secondly, assume that there exists J {⊂ \atop ≠}I such that f_{1}^{(J)}, …, f_{k}^{(J)} vanish identically. As W_{B} touches M_{I}, there exists a point x ∈ M_{I} ⋂ W_{B}; by defintion, g_{1}(x) > 0, …, g_{l}(x) > 0. Then g_{1}, …, g_{l} are positive everywhere in a ball B_{x}(r) for a suitable r > 0. Since x ∈ M_{I} ⊂ ∂\overline{M_{J}}, the open set B_{x}(r) ⋂ M_{J} in P_{J} is nonempty (and of dimension n − |J| + 1), and B_{x}(r) ⋂ M_{J} ⊂ W_{B} by definition of W_{B}.

Thus, W_{B} touches M_{J} and we get a contradiction with Proposition 1, which proves the proposition. □

The Main Lemma follows immediately from Proposition 2 and the following proposition.

Proposition 3. For any polynomials h_{1}, …, h_{m} ∈ IR[X_{1}, …, X_{n}] with degrees deg(h_{i}) ≤ d, the number of sets minimal (with respect to the inclusion) among the subsets {1} ⊂ I ⊂ {1, …, n} such that h_{1}^{(I)}, …, h_{m}^{(I)} vanish identically, does not exceed 2^{c(d)n}.

We prove the proposition by induction on d. For d = 1, each h_{i} = ∑_{1≤j≤n} α_{ij}X_{j} + α_{i}, 1 ≤ i ≤ m, is a linear polynomial. Let {1} ⊂ I ⊂ {1, …, n} be a minimal set for which h_{1}^{(I)}, …, h_{m}^{(I)} vanish identically. Then for each 1 ≤ i ≤ m, α_{i} = 0, ∑_{1≤j≤n} α_{ij} = 0, and I must contain all j with α_{ij} ≠ 0. Thus, either no such I exists, or there is a unique such I consisting of {1} and all j ∈ {1, …, n} for which there exists 1 ≤ i ≤ m such that α_{ij} ≠ 0. This proves the proposition for the induction base d = 1.

Inductive step. Let d > 1. Consider two cases. Denote 0 < c = _{\frac{1−c(d−1)}{1−c(d−1)+ \frac{1}{d} log_{2}( \frac{2^{d}}{2^{d}−1} )}} <

1. A set V ⊂ {X_{2}, …, X_{n}} is called a cover set if each monomial X_{1}^{β_{1}}, …, X_{n}^{β_{n}} occurring in at least one of the polynomials h_{1}, …, h_{m} contains a variable from V ∪ {X_{1}}.

1. In the first case there does NOT exist a cover set V of size |V | ≤ cn. We construct a set {b_{1}, b_{2}, …, b_{l}} of monomials occurring in at least one of h_{1}, …, h_{m} such that they are pairwise disjoint in the variables and contain only the variables from {X_{2}, …, X_{n}}. We add b_{1}, b_{2}, ⋯ sequentially until no additional monomial can be added without violating the property stated above. Clearly, b_{1}, …, b_{l} contain at most dl variables among {X_{2}, …, X_{n}}, and that these variables constitute a cover set. By assumption, we must have dl > cn. Observe that for any set {1} ⊂ I ⊂ {1, …, n} such that h_{1}^{(I)}, …, h_{m}^{(I)} vanish identically, the set {X_{i}, i ∈ I} should have a common variable with each monomial b_{1}, …, b_{l}. Therefore, the number of all such sets (taking into account that the monomials b_{1}, …, b_{l} are pairwise disjoint, and each has the degree at most d) I does not exceed

2^{n} (\frac{2^{d} − 1}{2^{d}})^{l} ≤ 2^{n} (\frac{2^{d} − 1}{2^{d}})^{\frac{cn}{d}} .  (1)

2. In the second case there exists a cover set V with |V | ≤ cn. Consider any minimal {1} ⊂ I such that h_{1}^{(I)}, …, h_{m}^{(I)} vanish identically. Let I_{0} = V \ {X_{i}, i ∈ I} and I_{1} = V ∩ {X_{i}, i ∈ I}. We uniquely expand h_{j}^{(I_{1}∪{1})} = X_{1}h_{j,X_{1}} + ∑_{γ=(···γ_{i}···)}(∏_{i∈I_{0}} X_{i}^{γ_{i}})P_{j,γ}, 1 ≤ i ≤ m, where the polynomials P_{j,γ}, h_{j,X_{1}} are in the variables X_{i} ∉ V. Note that P_{j,γ}, h_{j,X_{1}} depend on variables in I_{0}. Since V is a cover set, deg P_{j,γ} ≤ d − 1 for each multi-index γ; obviously deg(h_{j,X_{1}}) ≤ d − 1. Since h_{j}^{(I)} vanishes identically, the polynomials P_{j,γ}^{(I\I_{1})} also vanish identically, and furthermore, the polynomial h_{j,X_{1}}^{(I\I_{1})} vanishes identically as well. Thus, I \ I_{1} is a minimal set for which the polynomials P_{j,γ}^{(I\I_{1})}, h_{j,X_{1}}^{(I\I_{1})}, 1 ≤ j ≤ m, vanish identically, due to the minimality property of I. By inductive hypothesis there are at most 2^{c(d−1)(n−|V |)} possible choices of I \ I_{1}. Since there are at most 2^{|V |} possibilities for the choice of I_{1}, we have in all at most

2^{c(d−1)(n−|V |)}2^{|V |} ≤ 2^{c(d−1)n}2^{(1−c(d−1))cn}.  (2)

minimal sets I.

By the definition of c, it is straightforward to verify from (1), (2) that the number of minimal sets are no greater than 2^{c(d)n} in both cases. This completes the inductive step. We have thus proved Proposition 3, and hence Theorem 1. □

4 Proof of Theorem 2

Let T be any degree-d algebraic decision tree for deciding whether n − 1 input real numbers x_{2}, x_{3}, ⋯, x_{n} are all less than or equal to 0. We show that the size of T is at least 2^{n−1}/m_{d,n−1}. This implies Theorem 2, as any decision tree for MAX= with inputs x_{1}, x_{2}, ⋯, x_{n} can be converted into a decision tree for the above problem by setting x_{1} = 0.

The proof is analogous to the first half of the proof of Theorem 1. For each I ⊂ {2, 3, …, n}, let M_{I} = {(x_{2}, x_{3}, …, x_{n}) : x_{i} = 0 for i ∈ I, x_{j} < 0 for j ∉ I}. Let B be any branch of T, with f_{1} = ⋯ = f_{k} = 0, g_{1} > 0, …, g_{l} > 0 being the set of constraints along B; let W_{B} ⊂ IR^{n} denote the set of inputs (x_{2}, x_{3}, …, x_{n}) satisfying these constraints. We say that W_{B} touches M_{I} if dim(W_{B} ⋂ M_{I}) = dim M_{I} = n − 1 − |I|.

For any J ⊆ {2, 3, …, n} and a polynomial h ∈ IR[X_{2}, …, X_{n}], define the polynomial h^{(J)}(X_{j}, j ∉ J) = h|_{X_{j}=0,j∈J} ∈ IR[X_{j}, j ∉ J].

Similar to Proposition 2, we have the following.

Proposition 2′ If W_{B} touches M_{I}, then I is a minimal subset among all subsets J satisfying f_{i}^{(J)} ≡ 0 for 1 ≤ i ≤ k.

The proof of Proposition 2′ is virtually identical to that of Proposition 2. Note that if W_{B} touches M_{I}, then all the polynomials f_{j} have vanishing constant terms (i.e., f_{j}(0) = 0).

We want to rephrase Proposition 2′ in terms of hypergraphs. To do this, we first relate the “minimal subsets” to minimal cutsets for hypergraphs. For any h ∈ IR[X_{2}, …, X_{n}], let G_{h} denote the family of nonempty subsets {i_{1}, …, i_{q}} for which there exists a monomial of h with the set of variables {X_{i_{1}}, …, X_{i_{q}}}. Given a family H of polynomials, let G_{H} = ⋃_{h∈H} G_{h}. Note that G_{h} and G_{H} are hypergraphs.

Let H = {h_{1}, …, h_{m}} where h_{i} ∈ IR[X_{2}, …, X_{n}] are polynomials with no constant terms.

Proposition 4. For any J ⊂ {2, …, n}, h_{1}^{(J)} ≡ 0, …, h_{m}^{(J)} ≡ 0 if and only if J is a cutset of G_{H}.

Proof. If J is a cutset of G_{H}, then setting X_{j} to 0 for all j ∈ J kills all the monomials in h_{i}. Hence h_{i}^{(J)} ≡ 0 for all i. If, on the other hand, h_{i}^{(J)} ≡ 0 for all i, then for each i no monomials in h_{i} can be free from all X_{j}, j ∈ J, since otherwise h_{i}^{(J)} is not identically equal to 0. Thus, J is a cutset of G_{h_{i}}, and since G_{H} is a union of all G_{h_{i}}, J is a cutset of G_{H}. □

Proposition 4 implies that the sets minimal among I such that the polynomials h_{1}^{(I)}, h_{2}^{(I)}, …, h_{m}^{(I)} vanish identically are exactly the minimal cutsets of G_{H}.

Using Proposition 4, we can rephrase Propositions 2′ as follows: If W_{B} touches M_{I}, then I is a minimal cutset of G_{F} where F = {f_{1}, …, f_{k}}. Since G_{F} is of rank d or less, there are at most m_{d,n−1} such cutsets. This proves that W_{B} can touch at most m_{d,n−1} M_{I}’s. To touch all 2^{n−1} M_{I}’s, at least 2^{n−1}/m_{d,n−1} branches B are needed. Thus, T must have size at least 2^{n−1}/m_{d,n−1}. This completes the proof of Theorem 2.

References

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

[BFMUW87] A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson, A Time-Space Tradeoff for Element Distinctness, SIAM J. on Computing 16 (1987), pp. 97-99.

[BFKLT81] A. Borodin, M. Fischer, D. Kirkpatrick, N. Lynch, and M. Tompa, A Time-Space Tradeoff for Sorting on Oblivious Machines, J. of Computer and System Sciences 22 (1981), pp. 351-364.

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

[BLY92] A. Björner, L. Lovász, and A. Yao, Linear Decision Treees: Volume Estimates and Topological Bounds, Proc. 24th ACM STOC (1992), pp. 170-177.

[DL75] D. Dobkin and R.J. Lipton, On the complexity of computations under varying sets of primitives, in Automata Theory and Formal Languages (edited by H. Bradhage), Lecture Notes in Computer Science, Volume 33, Springer-Verlag, 1975, pp. 110-117.

[F93] R. Fleischer, Decision Trees: Old and New Results, Proc. 25th ACM STOC (1993), pp. 468–477.

[FG79] F. Fussenegger, H.N. Gabow, A Counting Approach to Lower Bounds for Selection Problems, J. Assoc. Comput. Mach. 25 (1979), pp.227-238.

[GS79] C. Gane and T. Sarson, Structured Systems Analysis: Tools and Techniques, Prentice Hall, Englewood Cliffs, NJ, 1979.

[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.

[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.

[K73] D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973.

[MM65] J. W. Moon, L. Moser, On Cliques in Graphs, Israel J. Math. 3(1965), pp. 23-28.

[MPR94] L. J. Montana, L. M. Pardo, T. Recio, A Note on Rabin’s Width of a Complete Proof, Computational Complexity, 4(1994), pp. 12-36.

[R72] M. O. Rabin, Proving Simultaneous Positivity of Linear Forms, J. Comput. Sci. 6 (1972), pp. 639–650.

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

[TY94] H. F. Ting and A. C. Yao, A Randomized Algorithm for Finding Maximum with O((log n)^{2}) Polynomial Tests, Information Processing Letters 49 (1994), pp. 39-43.

[Y75] A. C. Yao, On the Complexity of Comparison Problems Using Linear Functions, Proc. 16th IEEE FOCS (1975), pp. 85–89.

[Y82] A. C. Yao, On the Time-Space Tradeoff for Sorting with Linear Queries, Theoretical Computer Science 19 (1982), pp. 203-218.

[Y89] A. C. Yao, On Selecting the k Largest with Median Tests, Algorithmica 4 (1989), pp. 293–300.