A Lower Bound for Randomized Algebraic Decision Trees ^{∗}

Dima Grigoriev ^{†}  Marek Karpinski ^{‡}
Friedhelm Meyer auf der Heide ^{§} Roman Smolensky ^{¶}

Abstract

We prove the first nontrivial (and superlinear) lower bounds on the depth of randomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n^{2}) randomized lower bound for the Knapsack Problem, and an Ω(n log n) randomized lower bound for the Element Distinctness Problem which were previously known only 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 lower bound technique for deterministic algebraic decision trees without making use of Milnor’s bound on Betti number of algebraic varieties.

∗A preliminary version of this paper appeared in [GKMS96] †Dept. of Computer Science and Mathematics, Penn State University, University Park.

Research partially supported by NSF Grant CCR-9424358. Email: dima@cse.psu.edu

‡Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by DFG Grant KA 673/4-1, by the ESPRIT BR Grants 7097 and EC-US 030.

Email: marek@cs.uni-bonn.de

§Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn. Supported partially by DFG Grant ME 872/4-1 and ESPRIT BR Grant

7141 (ALCOMII). Email: fmadh@uni-paderborn.de

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

1 Introduction.

Starting with [MT85], [S85], [M85a] and [M85b] there has been a continued effort in the last decade to understand the 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. [Y81], [SY82], [B83], [BLY92], [Y92], [GKV97], [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 finite 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 problems being finite unions of hyperplanes as well as intersections of halfspaces. This provides also a new method for proving lower bounds 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).

The paper is organized as follows. Section 2 introduces randomized algebraic decision and computation trees. Section 3 overviews the known results in the area. Section 4 summarizes our results and applies them for a number of concrete problems. Section 5 gives an outline of the lower bound proof, and Sections 6 and 7 give the proof of the Main Theorem. Section 8 contains the complexity lower bound for deterministic decision trees under less restrictive conditions than in the Main Theorem for their randomized counterparts.

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

We deal in this paper with randomized algebraic decision trees of degree d, d-RDT s for short. There are several variants of this model known in the literature (see, e.g. [M85a], [M85b], [M85c], [MT85]). One of the most natural variants allows coin flipping nodes and charges for the random bits used. Other variants ignore the costs for random choices, or pull flipping nodes out of the decision trees, and view a d-RDT as a finite collection {T_{α}} of d-DT s T_{α} with the assigned (rational) probabilities p_{α}, ∑_{α} p_{α} = 1, of choosing T_{α} out of the collection {T_{α}}. In the latter case we also do not charge for the randomization. This variant is easily seen to be equivalent (up to constant factors in the depth) to the “equal likelihood” variant with all trees T_{α} having equal probabilities p_{α} (p_{α} = \frac{1}{|\{T_{α}\}|}). In this paper we use the last model mentioned above and define a d-RDT as a finite collection {T_{α}} of d-DT 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 (two-sided) error probability.

We note that the class of sets S ⊆ IR^{n} recognized by d-RDT s is closed under complement.

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]).

We note that RDT s are robust under changes of the error probability. This fact was first observed in [BG81], and then explicitely formulated and proven for RDT s in [M85c](Claim 1.3):

Fact 1 (Amplification): Let γ′, γ ∈ (0, \frac{1}{2}) be constants. Every d-RDT of depth T recognizing L ⊆ IR^{n} with error probability γ′ can be simulated by a d-RDT of depth O(T) recognizing L with error probability γ.

A standard notion of runtime of randomized algorithms is worst case expected time, i.e., the maximum over the expected runtimes of the algorithm started with input x, maximum taken over all inputs of length n. In [MT85] it is shown that any d-RDT with worst case expected time T can be simulated by one with depth O(T). Using Fact 1, the error probability can remain unchanged.

3 Known Results.

The most important results in connection to this research are the variants of the component counting lower bounds for deterministic computations: Let L ⊆ IR^{n} have q connected components. Then each LDT for L has depth Ω(log(q)) [DL78], each d-DT for L has depth Ω(\frac{log(q)}{log(d)} − n) (can be deduced from [B83], see also [SY82]), 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 problems.

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

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

A further important example is the Element Distinctness Problem [B83], with the connected components bound n!, and therefore a deterministic lower bound Ω(n log n). Other related problems are: Set Disjointness, Resultant, and the ε-Approximation Knapsack Problem (cf. [B83]).

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 [GK94].)

In [BKL93] it is shown that there are benefits if the randomization is used in CT s: Consider the language {(x, y) ∈ IR^{2n} : y is a 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 closed halfspaces. S is often called a linear arrangement, S^{+} is a polyhedron. A k-face L of S is a k-dimensional plane 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^{+}. 0-faces are also called vertices.

We prove the following lower bound.

Main Theorem: For any constants 0 ≤ γ < \frac{1}{2}, c_{1} > 0 and τ > δ ≥ 0, there exists a constant c_{0} > 0 satisfying the following. Let H_{1}, …, H_{m} be hyperplanes in IR^{n}, S = ⋃_{i=1}^{m} H_{i}, S^{+} = ⋂_{i=1}^{m} H_{i}^{+} for m ≥ n. If S or S^{+} has at least m^{τ(n−k)} k-faces for some k ∈ {0, …, n − 1}, then each d-RDT for S or S^{+} with error probability γ has depth greater than c_{0}(n − k) log(m), provided that d ≤ c_{1}m^{δ}.

Obviously, in a generic arrangement (when all the intersections of subfamilies of the hyperplanes are pairwise distinct) the number of k-faces equals \binom{m}{n−k} which is bounded from below by m^{Ω(n−k)}, provided that m ≥ Ω(n^{1+σ_{0}}) for some σ_{o} > 0, thus the bound on the number of k-faces from the theorem is attainable. In case of a polyhedron, the upper bound O(m^{min\{n−k,[ \frac{n}{2} ]\}}) [E87] on the number of k-faces is also attainable (for example for the dual to the cyclic polyhedra, see [M71], also [GKV97]).

Our Main Theorem yields directly the following concrete applications:

Corollary 1: For δ > 0 sufficiently small, the following randomized lower bounds hold.

(1.1) Ω(n^{2} log(s + 1)) is a lower bound for the depth of any d-RDT (with d = O((s + 1)^{δn})δ < \frac{1}{16}) recognizing the Integer Programming Problem L_{n,s}.

(1.2) Ω(n^{2}) is a lower bound for the depth of any d-RDT (with d = O(2^{δn}), δ < \frac{1}{16}.) recognizing the Knapsack Problem or the ε-Approximation Knapsack Problem.

Corollary 2: Ω(n log n) is a lower bound for the depth of any d-RDT (with d = O(n^{δ}), δ < \frac{1}{2}) for the following problems:

(2.1) Element Distinctness,

(2.2) Set Disjointness,

(2.3) Resultant (Decision Version).

Proof of Corollary 1: Observe that (1.1) entails (1.2). We prove now (1.1). Without loss of generality we assume that n = 8r for certain integer r. Our purpose is to prove that L_{n,s} = {x ∈ IR^{n}, ∃a ∈ \{0, …, s\}^{n} : xa = s\} contains at least (s + 1)^{\frac{n^{2}}{16}} vertices. Consider the following system of linear equations E_{j}, 1 ≤ j ≤ \frac{n}{2} in \frac{n}{2} variables x_{1}, …, x\frac{n}{2} : E_{1} : sx_{1} = s; E_{2} : sx_{2} = s; E_{3} : sx_{1} + sx_{2} + sx_{3} = s; E_{4} : sx_{1} + sx_{2} + sx_{4} = s. For any 0 ≤ l ≤ r − 2: E_{4l+5} : sx_{1} + sx_{4l+3} + x_{4l+4} + x_{4l+5} = s; E_{4l+6} : sx_{1} + sx_{4l+3} + x_{4l+4} + x_{4l+6} = s; E_{4l+7} : sx_{1} + x_{4l+5} + x_{4l+7} = s; E_{4l+8} : sx_{1} + x_{4l+5} + x_{4l+8} = s Obviously, the system K(X_{1}, …, X\frac{n}{2} ) = (s, …, s)^{T} has a unique solution x_{4l+1} = x_{4l+2} = (s + 1)^{l}; x_{4l+3} = x_{4l+4} = −(s + 1)^{l} for l = 0, …, r − 1.

Let C be any \frac{n}{2} × \frac{n}{2} matrix with the property that all its entries being integers in the range from 0 to s such that its columns with the numbers 4l + 1, 4l + 2, 4l + 3 for all 0 ≤ l ≤ \frac{n}{8} − 1, consist of zeroes. Consider the following n × n matrix

A(C) = ( \begin{matrix}I & C \\ 0 & K \end{matrix} )

where I is the unit \frac{n}{2} × \frac{n}{2} matrix.

Evidently, the linear n × n system A(C) · X = (s, …, s)^{⊤} has a unique solution X(C) = (x_{1}, …, x_{n}). Therefore, X(C) is a vertex of L_{n,s}.

Moreover, we claim that for different choices of above matrices C, C′ the respective vectors X(C) and X(C′) are different. Indeed, (x_{\frac{n}{2} +1}, …, x_{n}) = (1, 1, −1, −1, (s + 1), (s + 1), −(s + 1), −(s + 1), …, (s + 1)^{r−1}, (s + 1)^{r−1}, −(s + 1)^{r−1}, −(s + 1)^{r−1}). For i < \frac{n}{2} we have x_{i} = s − ∑_{0≤j≤r−1} a_{j}(s + 1)^{j}, a_{j} ∈ {0, …, s}, herewith i-th row of C equals to (a_{0}, 0, 0, 0, a_{1}, 0, 0, 0, a_{2}, 0, 0, 0, …, a_{r−1}, 0, 0, 0). Since 0 ≤ a_{j} ≤ s we get that the i-th components of the vectors X(C), X(C′) differ, provided that C and C′ differ in the i-th row.

Thus, we can choose (s+1)^{\frac{n^{2}}{16}} distinct matrices of the form C and thereby so many distinct vertices of L_{n,s} of the form X(C). In other words, in the application of the main theorem we have m = (s + 1)^{n}, k = 0 with at least (s + 1)^{\frac{n^{2}}{16}} = m^{\frac{1}{16} n} of 0-faces in the arrangement L_{n,s}. □

Proof of Corollary 2: The proof of (2.2) is similar to the proof of (2.1), and obviously (2.2) implies (2.3) (cf. [B83]). We give now a proof of (2.1). Observe that the faces of the arrangement ⋃_{i<j}{x_{i} = x_{j}} (which represents the Distinctness Problem) are in one-to-one correspondence with all partitions of the set {1, …, n} (except the partition into singletons {1}, …, {n}). Indeed, the partition A_{1} ∪⋯∪A_{k} = {1, …, n} corresponds to the face being the intersection of all the hyperplanes {x_{i} = x_{j}} for i, j ∈ A_{l}, 1 ≤ l ≤ k, and the dimension of this face equals to k. Taking k = \frac{n}{2} (let n be even w. l. o. g.) we obtain at least k! partitions A_{1}, …, A_{k} of the following form: for each permutation π ∈ S_{k}, put A_{i} = {i, k + π(i)}, 1 ≤ i ≤ k. Thus, in the application of the theorem we have k = \frac{n}{2} (provided that n is even), m = \binom{n}{2}, and the number of k-faces equal to k! ≥ m^{δ(n−k)}, for arbitrary δ < \frac{1}{2}. □

5 Outline of the Lower Bound Proof.

Assume that the arrangement s = ⋃_{1≤i≤m} H_{i} has a vertex v, then after a certain permutation one can suppose that the hyperplanes H_{i} = {x ∈ IR^{n} : a_{i}x = b_{i}}, 1 ≤ i ≤ n are affinely independent and {v} = H_{1} ∩ ⋯ ∩ H_{n}.

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^{−1}(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. [L84]) 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 [L84]). 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 the less number of 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 a generic point 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 (in Lemma 1 we utilize just introduced notations). The following chapters contain their proofs.

Lemma 1: Let T be a d-RDT (or an RCT) recognizing

a) an arrangement S = ⋃_{1≤i≤m} H_{i} for some hyperplanes H_{1}, …, H_{m} such that L = ⋂_{1≤i≤n−k} H_{i} is a k-face of S , or

b) a polyhedron S^{+} = ⋂_{1≤i≤m} H_{i}^{+} such that for each 1 ≤ l ≤ n−k ⋂_{l≤i≤n−k} H_{i} is (k + l − 1)-face of S^{+}, 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 3: 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 4: 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.

Proofs of Corollaries 3 and 4: Because of Lemma 1 there is a CT (resp. d-DT) T_{α} from the definition of an RCT (resp. d-RDT) satisfying the condition V ar^{(v;X_{1},...,X_{n})}(T_{α}) ≥ (1 − 2γ)^{2}n (here X_{1}, …, X_{n} denote the coordinate hyperplanes). Take a path in T_{α} with the testing polynominals f_{1}, …, f_{s} along it for which V ar^{(v;X_{1},...,X_{n})}(f_{1}, …, f_{s}) ≥ (1 − 2γ)^{2}n.

To complete the proof of the Corollary 3 we easily show by induction on l that the polynominals f_{1}, …, f_{l} (1 ≤ l ≤ s) depend on at most 2l variables among X_{1}, …, X_{n}, since any computation step along the path in T_{α} could introduce into the game at most two new variables (one could evidently view the sequence of computation steps along the path as a straight-line program in which each step is an arithmetic operation with at most two arguments). Therefore, s ≥ \frac{1}{2}V ar^{(v;X_{1},...,X_{n})}(f_{1}, …, f_{s}). To complete the proof of the corollary 4 we notice that each term lm(f_{i}^{(v;X_{1},...,X_{n})}), 1 ≤ i ≤ s, depends on at most d variables, hence s ≥ \frac{1}{d}V ar^{(v;X_{1},...,X_{n})}(f_{1}, …, f_{s}).

□

Let 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 (in-

verse lexicographically smallest) sequence of (n − k) indices such that L = H_{i_{1}} ∩…∩H_{i_{n−k}}, i.e. i_{n−k} is the maximal possible index such that H_{i_{n−k}} ⊃ L, and i_{n−k−1} < i_{n−k} is the maximal possible index such that H_{i_{n−k−1}} ⊃ L and dim H_{i_{n−k}} ∩ H_{i_{n−k−1}} = n − 2, and so on. We fix this canonical representation of L = H_{i_{1}} ⋂ … ⋂ H_{i_{n−k}} by means of the indices i_{n−k} > … > i_{1}.

Now we give the canonical representation of a k-face L of the polyhedron S^{+} = ⋂_{1≤i≤m} H_{i}^{+}. W.l.o.g. one could assume that dim S^{+} = n (indeed, otherwise one can replace d-RDT under consideration by d-RDT obtained by restricting this d-RDT on the plane, being the linear hull of S^{+}). For any k_{1}-dimensional face L_{1} of S^{+} there exist hyperplanes H_{j_{1}}, …, H_{j_{n−k_{1}}} such that L_{1} = H_{j_{1}} ⋂ … ⋂ H_{j_{n−k_{1}}}. Under a hyperface of a l-dimensional polyhedron we mean a (l − 1)-plane which is its face of the dimension (l − 1). W.l.o.g. one could assume that all hyperplanes H_{1}, …, H_{m} are hyperfaces of S^{+}.

By H_{0} denote the family of all hyperplanes H_{i} such that H_{i} ⊃ L and H_{i} is a hyperface of S^{+}. Since S^{+} is a convex polyhedron, any its face is an intersection of some its hyperfaces, in particular, any its face L_{1} which contains L ⊂ L_{1}, could be represented as L_{1} = ∩_{H_{i}∈H′_{0}}H_{i} for a suitable subfamily H′_{0} ⊂ H_{0}.

Assume that by recursion on l it is already produced a sequence of indices i_{n−k} > … > i_{n−k−l+1}, 0 ≤ l ≤ n − k − 1, such that H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l_{1}+1}} is (n − l_{1})-face of S^{+} for every 0 ≤ l_{1} ≤ l. Denote the polyhedron S_{l}^{+} = (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ S^{+}. In addition, a family H_{l} ⊂ {H_{1}, …, H_{i_{n−k−l+1}−1}} is produced such that for any H_{i} ∈ H_{l} (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ H_{i} contains L and is a hyperface of S_{l}^{+}, and vice versa any hyperface of S_{l}^{+} has the form (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ H_{i} for a certain H_{i} ∈ H_{l}. Hence any face L_{1} ⊃ L of S_{l}^{+} has the form L_{1} = (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ (⋂_{H_{i}∈H′_{l}} H_{i}) for a suitable subfamily H′_{l} ⊂ H_{l}.

To carry out the recursive step, take as i_{n−k−l} the maximal index such that H_{i_{n−k−l}} ∈ H_{l} (obviously, i_{n−k−l} < i_{n−k−l+1}). Then L_{0} = H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}} ⋂ H_{i_{n−k−l}} is a hyperface of S_{l}^{+}. Denote the polyhedron S_{l+1}^{+} = H_{i_{n−k−l}} ⋂ S_{l}^{+}. Take as H_{l+1} the family of all H_{i} ∈ H_{l} such that L_{0} ⋂ H_{i} is a hyperface of S_{l+1}^{+} (evidently, L_{0} ⋂ H_{i} ⊃ L since H_{i_{n−k−l}}, H_{i} ∈ H_{l}). Due to the choice of i_{n−k−l} we have H_{l+1} ⊂ {H_{1}, …, H_{i_{n−k−l}−1}}.

It remains to prove that for any hyperface L_{2} of S_{l+1}^{+} such that L_{2} ⊃ L, there exists H_{i} ∈ H_{l+1} such that L_{2} = L_{0} ⋂ H_{i}. According to the property of H_{l} there exist H_{j_{1}}, H_{j_{2}} ∈ H_{l} such that L_{2} = (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ H_{j_{1}} ⋂ H_{j_{2}} and L_{2}^{(1)} = (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ H_{j_{1}}, L_{2}^{(2)} = (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) ⋂ H_{j_{2}} are the hyperfaces of S_{l}^{+}. For any face of codimension 2 of a convex polyhedron there exist exactly two its hyperfaces containing this face, and furthermore this face coincides with the intersection of these two hyperfaces. Since the face L_{2} of S_{l}^{+} lies in three its hyperfaces L_{2}^{(1)}, L_{2}^{(2)}, L_{0}, we have either L_{2}^{(1)} = L_{0} or L_{2}^{(2)} = L_{0}. Let for definiteness L_{2}^{(2)} = L_{0}; then H_{j_{1}} ∈ H_{l+1} by the definition of H_{l+1}, and L_{2} = L_{0} ⋂ H_{j_{1}}, that completes the recursive step.

Thus, at the end of the recursion we obtain a flag of L (which we treat as the claimed canonical representation of the k-face L) H_{i_{n−k}} ⊃ H_{i_{n−k}} ⋂ H_{i_{n−k−1}} ⊃ … ⊃ H_{i_{n−k}} ⋂ H_{i_{n−k−1}} ⋂ … ⋂ H_{i_{1}} = L such that for each 0 ≤ l ≤ n − k H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}} is (n − l)-face of S^{+} (the recursion on l implies that dim (H_{i_{n−k}} ⋂ … ⋂ H_{i_{n−k−l+1}}) = n − l, cf. lemma 1). Just to satisfy these properties of the flag of L, the above inductive construction was required.

Let v_{L} be a generic point of L which belongs to no lower dimensional face of S or S^{+}. We choose a coordinate system (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) in a

an arbitrary way. Expanding each polynomial f ∈ IR[X_{1}, …, X_{n}] in the variables Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} we define its leading monomial (cf. beginning of this section) lm^{(v_{L})}(f) considering f as a polynomial from IR[Z_{1}, …, Z_{k}][Y_{1}, …, Y_{n−k}] ⊂ IR(Z_{1}, …, Z_{k})[Y_{1}, …, Y_{n−k}], i.e. first taking the monomials with the least degree in the variable Y_{n−k}, after that among them with the least degree in Y_{n−k−1} and so on till the variable Y_{1}. Let T′ be an d − DT. 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 or 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)} · (\frac{td}{c(n−k)})^{c(n−k)} · 6^{n−k}.

Using these lemmas it is easy to conclude the Main Theorem:

First consider a d-RDT for S or S^{+} with error probability γ ∈ (0, \frac{1}{2}) small enough such that β := τ − (1 − (1 − δ)c) > 0 , where c := (1 − 2γ)^{2} and τ, δ chosen as in the Main Theorem.

Then Lemma 1 yields for each k-face L of S or S^{+}: V ar_{k}^{(v_{L})}(T_{α}) ≥ c · (n − k) for at least a fraction of \frac{1−2γ}{2−2γ} of the T_{α}’s. Thus there is a T_{α} with V ar_{k}^{(v_{L})}(T_{α}) ≥ (1 − 2γ)^{2}(n − k) for \frac{1−2γ}{2−2γ} · N many k-faces L of S or S^{+}.

Therefore Lemma 2 implies that

\frac{1−2γ}{2−2γ} m^{β(n−k)} ≤ 3^{t}(\frac{t}{c(n−k)})^{c(n−k)} · c_{1}^{c(n−k)}6^{n−k} if d ≤ c_{1}m^{δ}.

This proves the lower bound claimed in the Main Theorem for the choice of γ described above. Using Fact 1 yields the Main Theorem for arbitrary γ ∈ (0, \frac{1}{2}). □

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 H_{n} ⊃ H_{n} ∩ H_{n−1} ⊃ ⋯ ⊃ H_{n} ∩ ⋯ ∩ H_{1} = {(0, …, 0)} is the canonical representation (flag) of 0-face {(0, …, 0)} (in both cases a), b)), and herewith the H_{i}’s, 1 ≤ i ≤ n, are defined by {x ∈ IR^{n} : x_{i} = 0}, in other words the linear transformation (y_{1}, …, y_{n}) ↦ v + A(y_{1}, …, y_{n}) is the identity.

b) Now let the d-RDT (or the RCT) recognize S^{+} = ⋂_{i=1}^{m} 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. We show that E ∈ S^{+}. Take any hyperplane H_{l} = {β_{1}X_{1} + ⋯ + β_{n}X_{n} + β_{0} = 0}, n + 1 ≤ l ≤ m given by a linear function L_{H_{l}} with β_{j} ∈ IR, 0 ≤ j ≤ n. We need to show that L_{H_{l}}(E) ≥ 0. Denote by 0 ≤ j_{0} ≤ n the index such that β_{0} = ⋯ = β_{j_{0}−1} = 0, β_{j_{0}} ≠ 0. It suffices to show that β_{j_{0}} > 0, this would entail that sgn(L_{H_{l}}(E)) = sgn(βj_{0}) > 0. Pick out an arbitrary point v_{n−j_{0}} = (x_{1}^{(n−j_{0})}, …, x_{j_{0}}^{(n−j_{0})}, 0, …, 0) ∈ ((H_{n} ∩ ⋯ ∩ H_{j_{0}+1}) ∩ S^{+}) \ H_{j_{0}}. Therefore, x_{j_{0}}^{(n−j_{0})} ≠ 0 and 0 ≤ L_{H_{j_{0}}}(v_{n−j_{0}}) = x_{j_{0}}^{(n−j_{0})} since v_{n−j_{0}} ∈ S^{+}.

���

Hence 0 ≤ sgn(L_{H_{l}}(v_{n−j_{0}})) = sgn(β_{j_{0}} · x_{j_{0}}^{(n−j_{0})}), therefore sgn(β_{j_{0}}) > 0, this implies that E ∈ S^{+}. Evidently, E_{i}^{(+)} ∉ S^{+}.

Easy counting yields that the probability of T_{α}’s that classify E and at least (1 − 2γ)^{2}n many E_{i}^{(+)}’s correctly is greater than \frac{1−2γ}{2−2γ}. Indeed, the probability of the set of all α for which T_{α} classifies wrong at least (1 − (1 − 2γ)^{2})n among E_{i}^{(+)}, 1 ≤ i ≤ n is less or equal to \frac{γn}{(1−(1−2γ)^{2})n} = \frac{1}{4(1−γ)}. Hence the probability of α such that T_{α} classifies E and at least (1 − 2γ)^{2}n among E_{i}^{(+)}, 1 ≤ i ≤ n correctly is greater or equal to (1 − γ − \frac{1}{4(1−γ)}) > \frac{1−2γ}{2−2γ}.

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 b) for ⋂_{i=1}^{m} H_{i}^{+}.

a) In case of T recognizing S = ⋃_{i=1}^{m} H_{i} consider the points E_{i}^{(0)} = (ε_{1}, …, ε_{i−1}, 0, ε_{i+1}, …, ε_{n}) ∈ S, 1 ≤ i ≤ n and argue as above, replacing E_{i}^{(+)} by E_{i}^{(0)}, 1 ≤ i ≤ n, and observing that the point E does not lie in the arrangement S. □

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}).

Consider the flag of L

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

13 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 neighborhood of v_{L}). For the hyperplane H_{i_{n−k}} we construct a vertex of the tree T being a son of the root of T , and mark it with this hyperplane H_{i_{n−k}}. We label this vertex if and only if Y_{n−k} divides one of f_{1}, …, f_{s}. 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 where the coordinates Y_{1}, …, Y_{n−k} correspond to hyperplanes H_{i_{1}}, …, H_{i_{n−k}}, respectively, and Z_{1}, …, Z_{k} are arbitrary coodinates in L with the origin at v_{L}. 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 − k levels of the tree T are already constructed. Consider any vertex w of T at ℓ-th level. To the vertex w leads the 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 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−ℓ}^{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 conclude that the degree

deg ( ∏_{1≤j≤s} f_{j}^{(ℓ+1)}) ≤ deg ( ∏_{1≤j≤s} f_{j}^{(ℓ)}) − (p − q_{0} + 1) (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.l.o.g. that Q ≤ R (if Q > R then set M(R, Q, D) = 0). When R = Q we have M(R, R, D) ≤ m · M(R − 1, R − 1, D) and thereby M(R, R, D) ≤ m^{R} by induction on R. When R > Q 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) 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 (1) 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

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}

for the number of leaves in T .

So far, we’ve considered one path of the d-decision 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 (by Stirling’s formula) that

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

which proves Lemma 2.

□

8 Lower bound on the complexity of deterministic decision trees.

For d − DT T′ which recognizes either an arrangement S or a polyhedron S^{+}, we can give the similar complexity lower bound Ω(log N) as in the main theorem, where N is the number of k-faces of S or S^{+}, without the restriction N ≥ m^{Ω(n−k)}, imposed in the theorem. This implies the theorem from [GKV97] in case of a polyhedron S^{+}. For arrangements S, it gives new proofs of the results from [SY82], [B83], without making use of Milnor’s bound on the Betti numbers of algebraic varieties.

Theorem 1: Any d − DT T′ recognizing S or S^{+} with N k-faces, has the depth t greater than \frac{1}{2}(log_{3} N − (n − k) log_{3} d).

The proof follows the proof of the Main Theorem with considerable simplifications. Namely, in Lemma 1 one states that

V ar^{(v;H_{1},...,H_{n−k})}(T′) = n − k

.

In Lemma 2 we have the bound N ≤ 3^{t}(\frac{td}{n−k})^{n−k}3^{n−k} due to the estimation M(n − k, 0, td) ≤ (\frac{td}{n−k})^{n−k}3^{n−k}.

□

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

[BG81] C.H. Bennett, J.Gill, Relative to a Random Oracle A, P^{A} ≠ NP^{A} ≠ co−NP^{A} with Probability 1, SIAM J.Comput. 10 (1981), pp. 96-113.

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

[E87] H. Edelsbrunner, Algorithms in Computational Geometry, Springer, 1987.

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

[GKMS96] D. Grigoriev, M. Karpinski, F. Meyer auf der Heide, R. Smolensky, A Lower Bound for Randomized Algebraic Decision Trees, Proc. ACM STOC (1996), pp. 612-619.

[GKV97] D. Grigoriev, M. Karpinski, N. Vorobjov, Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Discrete Comput. Geom. 17 (1997), pp. 191-215.

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

[L84] S. Lang, Algebra, Addison–Wesley, New York, 1984.

[M71] P. McMullen and G. Shephard, Convex Polytopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge (1971).

[M93] S. Meiser, Point Location in Arrangements of Hyperplanes, Information and Computation 106 (1993), pp. 286 – 303.

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

[MT85] U. Manber and M. Tompa, Probabilistic, Nondeterministic and Alternating Decision Trees, J. ACM, Vol. 32 (1985),pp. 720-732.

[S85] M. Snir, Lower Bounds for Probabilistic Linear Decision Trees, Theor. Comput. Sci., Vol. 38 (1985), pp. 69-82.

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

[Y81] A. Yao, A Lower Bound to Finding Convex Hulls, J. ACM 28 (1981), pp. 780–787.

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