ON COMPUTATIONAL POWER OF ANALYTIC AND

ALGEBRAIC RANDOMIZED DECISION TREES

Dima Grigoriev^{∗} Marek Karpinski^{†} Roman Smolensky^{§}

Abstract. We introduce a new method for proving lower bounds on randomized and deterministic analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design also randomized algebraic decision tree for recognizing the positive octant in ℝ^{n} or computing MAX in ℝ^{n+1} in depth log^{0(1)} n. Both problems are known to have linear lower lower bounds on the depth of any deterministic analytic decision tree recognizing them. The main proof idea of the paper is in the reduction of the signs of the testing functions in a decision tree to the signs of their leading terms at the specially chosen point. This allows us to reduce the complexity of a decision tree to the complexity of a certain boolean circuit.

1. Introduction.

The problem of obtaining complexity lower bounds on algebraic decision trees

has a long history (a recent overview of the known methods could be found, e.g.,

in [GKV95], see also [R72], [M85], [MPR94], [Y94], [GV96], [GKMS96]). However

almost all known results (with the interesting exception of [R72], [MPR94], and

[GV96]) concern algebraic decision trees, i.e. decision trees with the gate functions

being polynomials.

In this paper we introduce a new method for proving complexity lower bounds

for a stronger computational model of analytical decision trees, i.e. the trees with

the gate functions being analytic (cf. also [R72]).

∗ Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802. Supported in part by NSF grant CCR-9424358. E-mail: dima@cse.psu.edu

† Department of Computer Science, University of Bonn, 53117 Bonn, and International Computer Science Institute, Berkeley, CA. Supported in part by DFG Grant KA673/4-1, by the ES-PRIT BR Grants 7097 and EC-US 030, and by the Volkswagen-Stiftung. E-mail: marek@cs.bonn.edu

§ Department of Computer Science, University of Bonn, 53117 Bonn. Roman Smolensky died on 19 October, 1995 in New York. The main results of the paper were obtained in the Summer of 1995. This paper is also dedicated to the memory of Roman by the other co-authors.

Typeset by AMS-TEX

Let us briefly mention the main results of the paper.

In Section 3a, after describing the method we give a short proof for Rabin’s lower bound n (cf. [R72], [MPR95]) on the depth for testing membership to an octant ℝ_{+}^{n} = {(x_{1}, …, x_{n}) ∈ ℝ^{n} : x_{1} ≥ 0, …, x_{n} ≥ 0} by a deterministic analytic decision tree. In Section 3b we design a randomized algebraic decision tree (with the gates being polynomials of degrees at most n) which recognizes ℝ_{+}^{n} with the depth 0(log^{2} n). Furthermore, we design another randomized tree of the same type computing max{x_{1}, …, x_{n}} with the depth 0(log^{5} n). This extends the result of [TY94] which was for the case x_{1}, …, x_{n} being pairwise distinct only.

In Section 4 we study the size of analytic decision trees (which is a stronger complexity measure than the commonly considered depth, since a lower bound on the size implies immediately a lower bound on the depth). In particular, as a corollary we prove an exponential lower bound 2^{Ω(n)} on the size of analytic decision trees testing membership to the set of the points (x_{1}, …, x_{2n}) ∈ ℝ^{2n} with exactly n negative coordinates. Notice, that the only known so far exponential lower bound on the size of decision trees was obtained in [GKY95] for testing the octant ℝ_{+}^{n} under the assumption that the tree is ternary (i.e., branching according to the inequalities <, =, >) rather than a usual binary one (which branches according to ≤, >) and besides, the decision tree is algebraic if the gate functions are polynomials of a fixed degree.

Finally, in Section 5 we obtain a lower bound Ω(\sqrt{n}) on the depth of randomized analytic decision trees which recognize a set of the type {(x_{1}, …, x_{n}) : the number of negative elements among x_{1}, …, x_{n} is a multiple of q} for a fixed q being not a power of 2. Notice that this is the first nontrivial lower bound for randomized analytic decision trees (for randomized algebraic decision trees stronger, namely nonlinear, lower bound was proved in [GKMS96]).

A method for obtaining non-linear lower bounds on the depth of Pfaffian computation trees (which are the trees with the gates being Pfaffian functions and thus, lying between the algebraic and analytic decision trees) for the problem of testing membership to a polyhedron was developed in [GV96]. This result is however independent from the present paper since relying on the methods exhibited below, one could get only linear lower bounds on the depth.

2. Preliminaries.

Similarly as in [GKMS96], for a given polynomial g ∈ ℝ[X_{1}, …, X_{n}], we define its leading term lm(g) as follows. First we take the terms of g with the least degree in X_{n}, then among them with the least degree in X_{n−1} and so on, till X_{1}. One can describe lm(g) by means of infinitesimals (cf., e.g., [GKMS96]).

Namely for a real closed field F (see e.g. ([L65], [GV88]) 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 { \atop F (ε)} (see [L65]). Now let ε_{1} > ⋯ > ε_{n} > 0 be the elements such that ε_{ℓ+1} is infinitesimal with respect to the real closed field ℝ̃(ε) for ε = (ε_{1}, …, ε_{ℓ}), 0 ≤ ℓ < n. Then the sign sgn(g(ε_{1}, …, ε_{n})) = sgn(lm(g)(ε_{1}, …, ε_{n})) and on the other hand 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.

As computational models we deal with the decision trees (DT) (see e.g. [R72], [MPR94], [GKV95], [GKY95]). We consider two kinds of gates of DT: either polynomials of degrees at most d, then denote the corresponding algebraic decision trees by d-DT, or the functions, being real analytic (cf. [C48]) in a certain vicinity of the origin, then denote the corresponding analytic decision trees by A-DT. We denote by d-RDT or A-RDT, respectively, their randomized counterparts, called randomized decision trees, which are the sets {T_{α}} (see e.g. [M85], [GKMS96]), with T_{α} being a deterministic d-DT or A-DT, respectively, chosen with a probability p_{α} ≥ 0, ∑ p_{α} = 1.

Observe that for a function 𝔞 in n variables X_{1}, …, X_{n}, being real analytic at the origin, one can literally extend the notion of the leading term lm(𝔞) as above, treating 𝔞 as a power series in X_{1}, …, X_{n}. Also sgn(𝔞(ε_{1}, …, ε_{n})) = sgn((lm(𝔞))(ε_{1}, …, ε_{n})) holds, herewith the power series 𝔞(ε_{1}, …, ε_{n}) could be naturally considered as an element of the real closed field ℝ_{n}, where ℝ_{0} = ℝ and for each 0 ≤ i ≤ n−1 ℝ_{i+1} is the field of Puiseux series ∑_{j⩾0}p_{j}ε_{i+1}^{μ_{j}/∂}, p_{j} ∈ ℝ_{i}, 1 ≤ ∂ ∈ ℤ, integers μ_{0} < μ_{1} < … increase (see e.g. [GV88]). Since ℝ_{n} is a real closed field, due to Tarski’s transfer principle [T51], the sign sgn((lm(𝔞))(ε_{1}, …, ε_{n})) does not depend on, whether we regard (lm(𝔞))(ε_{1}, …, ε_{n}) as an element of the real closure { \atop ℝ(ε_{1}, …, ε_{n})} or of its extension ℝ_{n}.

3. Testing octant: deterministic vs. randomized decision trees. Testing membership to the nonnegative octant ℝ_{+}^{n} was firstly studied in [R72],

where a (sharp) lower bound n was formulated for the depth of A-DT (a gap in the proof was filled in [MPR94] for algebraic or Nash gate functions). In the next subsection we give a short proof of the bound for the case of analytic functions, closing also a gap in Rabin’s original proof [R72] for this case.

3a. Deterministic decision trees (Rabin’s theorem).

Let an A-DT T test membership to ℝ_{+}^{n}. For any vector σ = (σ_{1}, …, σ_{n}) ∈ {−1, 1}^{n} consider a point E_{σ} = (σ_{1}ε_{1}, …, σ_{n}ε_{n}) ∈ (ℝ_{n})^{n}. Consider any gate 𝔞 of T, being a real analytic function. For any point (ε_{1}^{(0)}, …, ε_{n}^{(0)}) ∈ ℝ^{n} where ε_{1}^{(0)} > ⋯ > ε_{n}^{(0)} > 0 and ε_{i+1}^{(0)} is sufficiently less than ϵ_{i}^{(0)}, 0 ≤ i ≤ n − 1, we have sgn(𝔞(σ_{1}ε_{1}^{(0)}, …, σ_{n}ε_{n}^{(0)})) = sgn((lm(𝔞))(σ_{1}ε_{1}^{(0)}, …, σ_{n}ε_{n}^{(0)})). Also sgn(𝔞(E_{σ})) = sgn((lm(𝔞))(E_{σ})) (cf. section 2 above), obviously sgn((lm(𝔞)) (σ_{1}ε_{1}^{(0)}, …, σ_{n}ε_{n}^{(0)})) = sgn((lm(𝔞))(E_{σ})). Thus, sgn(𝔞(E_{σ})) = sgn(𝔞(σ_{1}ε_{1}^{(0)}, …, σ_{n}ε_{n}^{(0)})) and thereby runs correctly for an input point E_{σ}.

Notice that the above argument was necessary since we deal with A-DTs. If we would consider d-DT rather than A-DT, we could immediately apply Tarski’s transfer principle [T51] to ensure that d-DT runs correctly for any input point from (ℝ_{n})^{n}. For the purpose of this paper the restriction on the input points E_{σ} for A-DT suffices.

Take the path in T along which T runs for the point E_{(1,...,1)} = (ε_{1}, …, ε_{n}) (and therefore, outputs “yes”). Let g_{1}, …, g_{t} be the testing (real analytical) functions along this path.

Lemma 1. t ≥ n

Proof. Denote lm(g_{j}) = c_{j}X_{1}^{s_{1,j}} ⋯ X_{n}^{s_{n,j}}, c_{j} ∈ ℝ, 1 ≤ j ≤ t. The sign sgn(lm(g_{j})) is determined by the vector S_{j} = (s_{1,j}, …, s_{n,j}) (mod 2) ∈ (𝔽_{2})^{n}, 1 ≤ j ≤ t. Suppose that t < n. Then there exists a nonzero vector (s_{1}, …, s_{n}) ∈ 𝔽_{2}^{n} such that the inner products ((s_{1}, …, s_{n}), S_{j}) = 0 (mod 2), 1 ≤ j ≤ t. Denote σ = ((−1)^{s_{1}}, …, (−1)^{s_{n}}). Then lm(g_{j}(E_{(1,...,1)}) = lm(g_{j}(E_{σ})), 1 ≤ j ≤ t; i.e. E_{σ} satisfies all the tests along the path under consideration, and thereby the output of T for the input E_{σ} is “yes”, but E_{σ} does not belong to the nonnegative octant, the obtained contradiction proves the lemma.

Corollary 1. ([R72])

Any A-DT testing membership to ℝ_{+}^{n} has the depth at least n.

3b. Randomized decision trees.

In [TY94] it was shown that testing membership to the octant ℝ_{+}^{n} can be performed by a n-RDT with the depth (log n)^{0(1)} under the assumption that all the coordinates of an input vector (x_{1}, …, x_{n}) ∈ ℝ^{n} are nonzeroes. In this subsection we design n-RDT testing membership to ℝ_{+}^{n} for arbitrary input vectors.

Thus, RDT (in particular n-RDT and A-RDT) could have much less depth than any DT solving the same problem, cf. corollary 1. On the other hand, in [GKMS96] it was proved the lower bound \frac{n}{2d} on the depth of d-RDT testing membership to ℝ_{+}^{n}. This shows that there is a noncollapsing hierarchy on the computational power of d-RDT with respect to d.

Let (x_{1}, …, x_{n}) ∈ ℝ^{n} be an input vector. Denote by P ⊂ {1, …, n} the subset of j such that x_{j} < 0. Treating {1, …, n} as a subset of V = (𝔽_{2})^{⌈log_{2} n⌉} (in an arbitrary way), we apply to P theorem 2.4 [VV86]. It states that for a random choice of vectors w_{1}, …, w_{⌈log_{2} n⌉} ∈ V the probability that one of the truncated sets P_{ℓ} = P ∩ {v ∈ V; (v, w_{i}) = 0, 1 ≤ i ≤ ℓ}, 0 ≤ ℓ ≤ ⌈log_{2} n⌉ consists of a single element is at least 1/4 (provided that P ≠ ϕ). For any 1 > δ > 0 making 0(log 1/δ) rounds of choosing the vectors w_{1}, …, w_{⌈log_{2} n⌉}, we could achieve the latter probability to be greater than 1 − δ (for at least one of the rounds).

For the next step we need to be able to pick out randomly a homogeneous multilinear polynomial h_{k} from ℝ[Y_{1}, …, Y_{m}] of degree k (for 0 ≤ k ≤ m) and with all the coefficients in the interval [0, 1]. In fact, one could pick out randomly from a suitable finite set of such polynomials, or one could use the general statement from [M85] which enables us for a randomized decision tree with a continuous random parameter to replace it by a discrete one. For the reason of simplicity we will use a continuous random parameter.

Thus, fix for the time being a chosen randomly truncated set {v ∈ V; (v, w_{i}) = 0, 1 ≤ i ≤ ℓ} = {j_{1}, …, j_{m}}. Denote {Y_{1}, …, Y_{m}} = {X_{j_{1}}, …, X_{j_{m}}}. Observe that a random homogeneous multilinear polynomial h_{k} ∈ ℝ[Y_{1}, …, Y_{m}] vanishes (with the probability 1) at the point (y_{1}, …, y_{m}) = (x_{j_{1}}, …, x_{j_{m}}) if and only if the number of zeroes among y_{1}, …, y_{m} is greater than m − k (if the latter is not fulfilled it vanishes with the probability zero).

We construct an n-RDT T, which using binary search is testing h_{⌈m/2⌉}(y_{1}, …, y_{m}), then testing h_{⌈m/4⌉}(y_{1}, …, y_{m}) if the first test returns zero, or else testing h_{3⌈m/4⌉} (y_{1}, …, y_{m}) and so on, finds the minimal k_{0} for which h_{k_{0}}(y_{1}, …, y_{m}) vanishes. Then m − k_{0} + 1 equals (with the probability 1) to the number of zeroes among y_{1}, …, y_{m}. Test also h_{k_{0}−1}(y_{1}, …, y_{m}), unless k_{0} = 1 and in this case (y_{1}, …, y_{m}) = (0, …, 0) and we agree 1 ≥ h_{0} ≥ 0. If all y_{1}, …, y_{m} were nonnegative (in particular, if (x_{1}, …, x_{n}) ∈ ℝ_{+}^{n}) then the latter test would be positive. If among y_{1}, …, y_{m} was exactly one negative element then the latter test would be negative (with the probability 1).

Summarizing, T makes 0(log 1/δ) rounds, choosing at every round some vectors w_{1}, …, w_{⌈log_{2} n⌉}, then for each truncated set (y_{1}, …, y_{m}) finds k_{0} as described above and tests h_{k_{0}−1}(y_{1}, …, y_{m}). If all these tests are positive, then T returns (x_{1}, …, x_{n}) ∈ ℝ_{+}^{n}, else if at least one of the tests is negative, T returns (x_{1}, …, x_{n}) ∉ ℝ_{+}^{n}.

It is not difficult to see the correctness of T in testing membership to ℝ_{+}^{n}. Indeed, if (x_{1}, …, x_{n}) ∈ ℝ_{+}^{n} then all the described tests h_{k_{0}−1}(y_{1}, …, y_{m}) are positive. Else, if (x_{1}, …, x_{n}) ∉ ℝ_{+}^{n} then with the probability greater than 1−δ one of the truncated sets (y_{1}, …, y_{m}) contains a single negative element. Then for this truncated set the test h_{k_{0}−1}(y_{1}, …, y_{m}) would be negative.

Now complete the depth analysis of T. There are 0(log 1/δ) rounds choosing vectors w_{1}, …, w_{⌈log_{2} n⌉}, each of these vectors yields a truncated set {y_{1}, …, y_{m}} ⊂ {x_{1}, …, x_{n}}. For every of these truncated sets T finds k_{0} by binary search, which in its turn also requires 0(log n) steps. Thus, the depth of n-RDT T can be bounded by 0(log^{2} n log 1/δ).

As an application of the described n-RDT one could design n-RDT with a similar depth 0(log^{2} n log 1/δ) and the probability greater than 1 − δ for the problem MAX = (cf. [TY94], [GKY95]), namely, whether x_{1} = max{x_{1}, …, x_{n}} for an input vector (x_{1}, …, x_{n}). It suffices to apply T to the vector (x_{1} − x_{2}, …, x_{1} − x_{n}) ∈ ℝ^{n−1}.

If one would like to solve the MAX problem (i.e. computing max{x_{1}, …, x_{n}}), then similarly as in [TY94] it is necessary to have a subroutine which increases a candidate for max{x_{1}, …, x_{n}}, in other words, which finds an element x_{j} greater than x_{1} (provided that such x_{j} does exist). It corresponds to detecting negative coordinate among x_{1} − x_{2}, …, x_{1} − x_{n} (provided, it does exist).

Namely, when a truncated set (y_{1}, …, y_{m}) with the negative test h_{k_{0}−1}(y_{1}, …, y_{m}) is found, we use the binary search to test as above, whether for the set (y_{1}, …, y_{⌈m/2⌉}) for the maximal k_{1} for which h_{k_{1}−1}(y_{1}, …, y_{⌈m/2⌉}) does not vanish, the inequality h_{k_{1}−1}(y_{1}, …, y_{⌈m/2⌉}) < 0 holds. If this is the case, then proceed to the half (y_{1}, …, y_{⌈m/2⌉}), else if h_{k_{1}−1}(y_{1}, …, y_{⌈m/2⌉}) > 0, then proceed to the half (y_{⌈m/2⌉}, …, y_{m}), and so on. If (y_{1}, …, y_{m}) contained a single negative element after ⌈log_{2} m⌉ steps, the described subroutine would find it. Thus, the depth of n-RDT for the described subroutine which finds a negative element among x_{1}, …, x_{n} (or returns that (x_{1}, …, x_{n}) ∈ ℝ_{+}^{n}) is bounded by 0(log^{3} n·log 1/δ). The probability of the correct output is greater than 1 − δ.

Finally, in [TY94] it is shown that the result of applying the procedure of finding a greater element among x_{1}, …, x_{n}, successively 0(log n) times, taking δ = 0(1/n) equals to max{x_{1}, …, x_{n}} with the probability close to 1. Thus, one can compute max({x_{1}, …, x_{n}} by n-RDT with the depth 0(log^{5} n).

Let us summarize what we have proved in this subsection in the following theorem. Theorem 1. For each of the following problems there is an n-RDT which for any input vector (x_{1}, …, x_{n}) ∈ ℝ^{n}

a) tests membership to ℝ_{+}^{n} or tests whether x_{1} = max{x_{1}, …, x_{n}} in the depth 0(log^{2} n);

b) finds a negative x_{i} (or returns that (x_{1}, …, x_{n}) ∈ ℝ_{+}^{n}) in the depth 0(log^{3} n)

c) computes i such that x_{i} = max{x_{1}, …, x_{n}} in the depth 0(log^{5} n).

4. Exponential lower bound on the size of deterministic analytic decision trees.

In this section we study the size of a decision tree as its complexity measure rather than its depth. Evidently, a lower bound on the size immediately implies a (logarithmic) lower bound on the depth, so it is a more difficult problem, and the known methods for obtaining lower bounds on the depth (see e.g. [GKV95] and the references there) do not give any lower bound on the size. Besides, as a counterpart to Rabin’s linear lower bound on the depth for testing membership to ℝ_{+}^{n} (see section 3a) an upper linear bound on the size is obvious. The point is that we deal usually with the binary decision trees (i.e. branching at ≤ or >). In [GKY95] ternary decision trees were studied (i.e. branching goes according to <, =, >) and an exponential lower bound on the size for testing membership to ℝ_{+}^{n} was obtained for algebraic d-DT where d = const. However, the result of [GKY95] cannot be deduced from the methods of this section since these methods work for binary decision trees, and on the other hand for binary trees there is already mentioned above obvious linear upper bound on the size for testing ℝ_{+}^{n}. Thus, the lower bounds on the size for binary and ternary trees are independent.

In this section we design a method for obtaining the first exponential lower bounds on the size of binary analytic decision trees, and we provide some concrete examples of the problems for which the sizes of A-DTs are exponential.

Consider an A-DT T. As in the subsection 3a we restrict T to the inputs E_{σ}. In this setting we attach to T a function b : {−1, 1}^{n} → {−1, 1} which maps σ to 1 if and only if E_{σ} is accepted by T (to each accepting (resp. rejecting) leaf of T 1 (resp. −1) is attached). One could treat b as a boolean function (cf. [BS90], [KM91]) and also as an element of a bigger set B_{n} of functions {−1, 1}^{n} → ℝ which is isomorphic to ℝ^{2^{n}}. Then B_{n} is ℝ-space with the basis of all multilinear monomials {X^{I} = X_{1}^{i_{1}} … X_{n}^{i_{n}}}; i_{1}, …, i_{n} ∈ {0, 1}.

Thus, for a boolean function b we have an expansion b = ∑_{I} β_{I}X^{I}, herewith the norm L_{2}((β_{I})_{I}) = ∑_{I} β_{I}^{2} = 1 (since the vector (β_{i})_{I} is an image of the vector \frac{1}{(\sqrt{2})^{n}} (b(x))_{x} with L_{2}-norm equal to 1 under the unitary Fourier transform being n-th tensor power of the matrix \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ). The important feature of b studied in [BS90], [KM91] is its L_{1}-norm L_{1}(b) = ∑_{I} |β_{I}|. We use the following lemma from [KM91] for which we give here also a short proof.

Lemma 2. ( [KM91]) If the tree T has m leaves then L_{1}(b) ≤ m.

Proof. As we restrict T to the inputs E_{σ} we could replace each gate g of T by lm(g)

(see subsection 3a). Thereby, to any subtree T′ of T we could assign a (boolean) function b_{T′} : {−1, 1}^{n} → {−1, 1}, then b is assigned to the whole tree T.

We prove lemma by induction on the size of the tree. In case of the base of induction the tree consists of a single leaf with constant 1 or −1 boolean function attached. For the inductive step consider a term lm(g) = c X^{I}, c ∈ ℝ in the root v of T and let the boolean functions b^{(1)}, b^{(2)} are attached to two subtrees T^{(1)}, T^{(2)} of T with the roots being the sons of v. Then b = \frac{1}{2}(1 − X^{I})b^{(1)} + \frac{1}{2}(1 + X^{I})b^{(2)} and hence L_{1}(b) ≤ L_{1}(b^{(1)}) + L_{1}(b^{(2)}). Then applying inductive hypothesis to the subtrees T^{(1)}, T^{(2)} completes the proof of the lemma.

To exhibit an example of a set, for which the membership requires an exponential size for any A-DT T, denote by C_{σ} = {σ_{1}X_{1} > 0, …, σ_{n}X_{n} > 0}, σ_{1}, …, σ_{n} ∈ {−1, 1} an octant. Assume that T recognizes membership to a set M such that

∪_{σ∈M}C_{σ} ⊂ M ⊂ ∪_{σ∈M}C_{σ} ∪ {X_{1} … X_{n} = 0} for a certain set M ⊂ {−1, 1}^{n}, i.e. the

inner part of M coincides with ∪_{σ∈M}C_{σ}. Denote by b_{M} : {−1, 1}^{n} → {−1, 1} the boolean function such that b_{M}(σ) = −1 if and only if σ ∈ M.

Lemma 2 provides the lower bound L_{1}(b_{M}) on the size of a decision tree T testing the set M. Now we give two examples of sets M with a big norm L_{1}(b_{M}) taken from [BS90].

Let n = 2k and define M_{EXACT} ⊂ ℝ^{n} to be the set of points (x_{1}, …, x_{n}) with exactly k negative coordinates among x_{1}, …, x_{n}.

Now let n = 4k and define M_{4} ⊂ ℝ^{n} to be the set of all the points (x_{1}, …, x_{n}) such that for each 0 ≤ i ≤ k − 1 either x_{4i+1}, x_{4i+2} are both negative or x_{4i+3}, x_{4i+4} are both negative.

Using the bounds L_{1}(b_{M_{EXACT}}) ≥ 2^{k}/k (observe that this bound is close to the possible largest bound due to the Cauchy inequality L_{1}(b) ≤ 2^{n/2} for any boolean function b ∈ B_{n}), L_{1}(b_{M_{4}}) ≥ (1.25)^{k} [BS90] and Lemma 2 we get the following corollary.

Corollary 2. Any analytic decision tree testing membership to a) M_{EXACT} or to b) M_{4} has the size greater than 2^{Ω(n)}.

5. Lower bound on the depth for randomized analytic decision trees. We have shown in Section 3 that randomization can enhance dramatically the

efficiency of analytic decision trees. In this section we a prove lower bound Ω(\sqrt{n}) for randomized analytic decision trees recognizing sets like L_{i,q} = ∪_{σ (mod q)≡i}C_{σ}, where the union is taken over σ ∈ {−1, 1}^{n} such that the number of −1 in σ has a residue i (mod q), and q is not a power of 2.

Thus, assume A-RDT T^{(i,q)} = {T_{α}} with the depth t recognizes L_{i,q}. Assuming that q is small (say, a constant), one can suppose q to be an odd prime, taking into account that the complexities of recognizing L_{i,q} for diverse i (and fixed q) coincide. Indeed, in order to reduce recognizing L_{i,q} to recognizing L_{j,q} one replaces the input (x_{1}, …, x_{n}) by (−x_{1}, …, −x_{j−i}, x_{j−i+1}, …, x_{n}).

Again as in the previous section we restrict T^{(i,q)} to the set of 2^{n} points E_{σ} and take A-DT T_{α} which makes at most \frac{1}{3}2^{n} errors on the points E ⊂ \{E_{σ}\}_{σ}, i.e. |E| ≤ \frac{1}{3}2^{n}. Again as in Section 4 we associate with T_{α} a boolean function b_{α}, but unlike Section 4 in a more standard setting, namely b_{α} : {0, 1}^{n} → {0, 1} = 𝔽_{2}. For each gate g (being an analytic function) of T_{α} consider lm(g) = cX_{1}^{i_{1}} ⋯ X_{n}^{i_{n}} and replace g by a linear form L_{g}(y_{1}, …, y_{n}) = i_{1}y_{1} +⋯+i_{n}y_{n} (mod 2) : 𝔽_{2}^{n} → 𝔽_{2}. To every path of T_{α} with the gate functions g_{1}, …, g_{k}, we attach the product of linear functions (L_{g_{1}} + τ_{1}) ⋯ (L_{g_{k}} + τ_{k}) where τ_{i} ∈ {0, 1}, 1 ≤ i ≤ k is the corresponding sign of the branch at the path with the gate function g_{i}. Then b_{α} coincides with the sum of the products (L_{g_{1}} + τ_{1}) ⋯ (L_{g_{k}} + τ_{k}) attached to all the paths with the outputs 1. Similar to Section 4 we can give an inductive description of b_{α}. For the base of induction consider a tree consisting of a single leaf and b_{α} equals to the output of this leaf. For the inductive step let the gate g be assigned at the root v of T_{α} and the boolean functions b^{(1)}, b^{(2)} are attached to the left and right subtrees, respectively, with the roots being the sons of v. Then b_{α} = L_{g} · b^{(1)} + (L_{g} + 1)b^{(2)}.

Therefore, deg b_{α} ≤ t. Thus, b_{α} coincides with the boolean function MOD_{i,q} at more than \frac{2}{3}2^{n} points, and hence the Corollary and Lemma 4 [S87] imply that deg b_{α} ≥ Ω(\sqrt{n}) for a certain 0 ≤ i ≤ q − 1, see above (to apply directly Corollary [S87] one has to imbed the functions b_{α}, MOD_{i,q} in the set of functions {0, 1}^{n} → 𝔽_{2^{ℓ}} for a suitable extension 𝔽_{2^{ℓ}} of 𝔽_{2}, cf. lemma 5 [S87]). Thus, we get the following theorem.

Theorem 2. Any A-RDT which recognizes the union of octants ∪_{σ (mod q))≡i}C_{σ} has the depth greater than Ω(\sqrt{n}) (for a fixed q being not a power of 2).

6. Open Problems and Further Research.

There remain important open problems on randomized decision complexity of many concrete problems which are expressible by simultaneous positivity of small degree polynomials, like quadratic or cubic ones. The interesting examples include Element Distinctness in algebraic computation tree model or for n-RDTs (cf. a randomized lower bound Ω(n log n) [GKMS96] for n^{δ}-RDTs with sufficiently small δ > 0), Finite Union of Balls in ℝ^{n}, or algebraic version of 3SAT being the problem of simultaneous positivity of cubic polynomials.

Acknowledgement.

We thank Andy Yao for many stimulating discussions on the subject of the paper.

References

[BS90] J. Bruck, R. Smolensky, Polynomial threshold functions, AC^{0} functions and spectral norms., Proc. IEEE FOCS, 1990, p. 632–641.

[C48] R.Courant, Theory of Functions of a Complex Variable, New York University Press, 1948.

[GV88] D. Grigoriev, N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, J. Symb. Comput., 1988, 5, p. 37–64.

[GV96] D. Grigoriev, N. Vorobjov, Complexity lower bounds for computation trees with elementary transcendental function gates, Theor. Comput. Sci., 1996.

[GKMS96] D. Grigoriev, M. Karpinski, F. Meyer auf der Heide, R. Smolensky, A lower bound for randomized algebraic decision trees, to appear in Proc. ACM STOC, 1996.

[GKV95] D. Grigoriev, M. Karpinski, N. Vorobjov, Improved lower bound on testing membership to a polyhedron by algebraic decision trees, Proc. IEEE FOCS, 1995, p. 258–265.

[GKY95] D. Grigoriev, M. Karpinski, A. Yao, An exponential lower bound on the size of algebraic decision trees for MAX, Technical Report TR-95-066, International Computer Science Institute, Berkeley, 1995; submitted to Computational Complexity.

[KM91] E. Kushilevitz, Y. Mansour, Learning decision trees using the Fourier spectrum, Proc. ACM STOC, 1991, p. 455–464.

[L65]S. Lang, Algebra, Addison-Wesley, 1965.

[M85] F. Meyer auf der Heide, Simulating Probabilistic by Deterministic Algebraic Computation Trees, Theor. Comput. Sci., 1985, 41, p. 325-330.

[MPR94] L. Montana, L. Pardo, T. Recio, A note on Rabin’s width of a complete proof, Comput. Complexity 1994, 4, p. 12–36.

[R72] M. Rabin, Proving simultaneous positivity of linear forms, J. Comput. Syst. Sci., 1972, 6, p. 639–650.

[S87]R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity,

Proc. ACM STOC, 1987, p. 77–82.

[T51] A. Tarski, A decision method for elementary algebra and geometry, University of California Press, 1951.

[TY94] H. Ting, A. Yao, A randomized algorithm for find maximum with 0(log^{2} n) polynomial tests, Inform. Processing Letters 49, 1994, p. 39–43.

[VV86] L. Valiant, V. Vazirani, NP is as easy as detecting unique solutions, Theor. Comp. Sci., 1986, 47, p. 85–93.