Randomized Complexity Lower Bounds

D. Grigoriev^{1}

Departments of Mathematics and Computer Science

The Pennsylvania State University

University Park, PA 16802 dima@cse.psu.edu

The complexity lower bound Ω(log N) is proved for randomized computation trees (over reals with branching signs {≤, >}) for recognizing an arrangement or a polyhedron with N faces. A similar lower bound is proved for randomized computation trees over any zerocharacteristic field with branching signs {=, ≠} for recognizing an arrangement. As consequences, this provides in particular, the randomized lower bound Ω(n^{2}) for the KNAPSACK problem (which was proved in case of the randomized computation trees over reals in [11]) and also the randomized lower bound Ω(n log n) for the DISTINCTNESS problem (which is thereby the sharp bound). The technical core of the paper is a lower bound on the multiplicative complexity of a polynomial in terms of its singularities.

Introduction.

The complexity lower bounds for deterministic algebraic computation trees were obtained in [26], [2], [4], [29], [30], [22] where the topological methods were developed. In particular, these methods provide the lower bound Ω(log N) for recognizing a union of planes (of different dimensions) with N faces, under a face we mean any nonempty intersection of several among these planes. As consequences we obtain the lower bound Ω(n log n) for the DISTINCTNESS problem ⋃_{1≤i<j≤n}{X_{i} = X_{j}} ⊂

IR^{n}, EQUALITY SET problem {(x_{1}, …, x_{n}, y_{1}, …, y_{n}) : (x_{1}, …, x_{n}) is a permutation of (y_{1}, …, y_{n})} ⊂ IR^{2n} and the lower bound Ω(n^{2}) for the KNAPSACK prob-

lem ⋃_{I⊂{1,...,n}} {∑_{i∈I}x_{i} = 1} ⊂ IR^{n}. In [14], [15] a differential-

1Supported by NSF Grant CCR-9424358. geometric approach for recognizing polyhedra (to which the mentioned topological methods are not applicable) was proposed which gives the lower bound Ω(log N/ log log N) where N is the number of faces of the polyhedron.

The first results on the randomized computation trees (RCT) appeared in [24], [19], [9], [10] but for decade an open problem remained to obtain non-linear complexity lower bounds for recognizing natural problems by RCT. In

[13] for the first time the nonlinear lower bound was obtained for somewhat weaker computational model of the randomized algebraic decision trees in which the testing polynomials in the branching nodes are of a fixed degree, rather than the computation trees in which the testing polynomials are computed along the path of the computation, so they could have in principle an exponential degree. The approach of [13] provides the lower bound Ω(log N) for recognizing an arrangement, i.e. a union of hyperplanes, and for recognizing a polyhedron, where N is again the number of faces. In particular, this leads to the lower bound Ω(n log n) for the DISTINCT-NESS problem and Ω(n^{2}) for the KNAPSACK problem. For the EQUALITY SET problem a complexity lower bound on a randomized algebraic decision tree seems to be an open question.

But the method of [13] does not provide a lower bound for more interesting model of RCT. Only in [11] a method was developed which gives in particular, a lower bound Ω(n^{2}) for the KNAPSACK problem on RCT. This method relies on the obtained in [11] lower bound on the multiplicative border complexity of polynomials. The lower bound Ω(log N) of [11] holds for arrangements or polyhedra which satisfy some special conditions which fail, for example, for the DISTINCT-NESS problem.

In this paper we consider RCT over an arbitrary zero-characteristic field F with branching signs {=, ≠} and also more customary RCT over reals with branching signs {≤, >}. We remind (see e.g. [24], [19], [13]) that RCT T = {T_{α}}_{α} is a collection of computation trees T_{α} which are chosen with the probabilities p_{α} ≥ 0, ∑_{α} p_{α} = 1 such that T gives for any input a correct output with a probability greater than 1 − γ for a certain γ < 1/2 which is called the error probability of RCT.

Let H_{1}, …, H_{m} ⊂ F^{n} be a family of hyperplanes, denote by S = H_{1} ∪ ⋯ ∪ H_{m} the arrangement. Under k-face of S we mean any nonempty intersection H_{i_{1}} ∩ ⋯∩H_{i_{n−k}} of the dimension dim(H_{i_{1}} ∩⋯∩H_{i_{n−k}}) = k.

Theorem 1. Assume that for a certain constant c_{0} < 1 any subarrangement S_{1} = H_{i_{1}} ∪ ⋯ ∪ H_{i_{q}} of S where q > c_{0}m, has at least N^{(0)} faces of all the dimensions. Then the depth of any RCT over F recognizing S, is greater than Ω(log_{2} N^{(0)} − 2n − log_{2} n).

Corollary 1.1. Any RCT over F solving the DIS-TINCTNESS problem, has the complexity greater than Ω(n log n).

The idea of the proof of the necessary in theorem 1 lower bound on N^{(0)} one can find in [13]. Observe that the lower bound in the corollary is nearly sharp since it is possible to compute (deterministically) the discriminant ∏_{1≤i<j≤n}(X_{i}−X_{j}) with the complexity O(n log^{2} n)

([20], [27]). If to count only nonscalar multiplications/divisions (i.e. to consider the multiplicative complexity) then the lower bound from the corollary becomes sharp also due to [20], [27].

Corollary 1.2. Any RCT over F solving the KNAP-SACK problem, has the complexity greater than Ω(n^{2}).

The proof of the necessary lower bound on N^{(0)} one can find in [11].

Corollary 1.2 can be generalized to the complexity lower bound Ω(n^{2} log j) for RCT solving the RE-STRICTED INTEGER PROGRAMMING ([19]) ⋃_{a∈{0,...,j−1}^{n}} ⊂

F^{n} (obviously, it converts into the KNAPSACK problem when j = 2).

In case of more customary RCT over reals IR with the branching signs {≤, >} we consider recognizing either an arrangement S = ∪_{1≤i≤m}H_{i} ⊂ IR^{n} or a polyhedron S^{+} = ∩_{1≤i≤m}H_{i}^{+} ⊂ IR^{n}, where H_{i}^{+} is a half-space bounded by the hyperplane H_{i}, 1 ≤ i ≤ m. We say that Γ = H_{i_{1}} ∩⋯∩H_{i_{n−k}} is k-face of S^{+} if dim(Γ∩S^{+}) = k.

Theorem 2. Let for some positive constants c, c_{1} and k ≤ (1 − c_{1})n an arrangement S = S = ∪_{1≤i≤m}H_{i} or a polyhedron S = S^{+} = ∩_{1≤i≤m}H_{i}^{+} have at least Ω(m^{c(n−k)}) k-faces. Then for any RCT recognizing S, its depth is greater than Ω(n log m).

Corollary 2.1. Any RCT over reals solving the DISTINCTNESS problem, has the complexity greater than Ω(n log n).

Similar to the case of RCT over a zero-characteristic field (cf. corollary 1.1) the complexity bound is sharp since one can (deterministically) sort the input real numbers x_{1}, …, x_{n} with the complexity O(n log n).

Corollary 2.2. (see also [11]). Any RCT over reals solving the KNAPSACK problem, has the complexity greater than Ω(n^{2}).

For the similar to the DISTINCTNESS problem SET DISJOINTNESS {(x_{1}, …, x_{n}, y_{1}, …, y_{n}) : x_{i} ≠ y_{j}} ⊂ IR^{2n} (being a complement to an arrangement) one obtains (almost literally as in the corolla ries 1.1, 2.1) the lower bound Ω(n log n) and the upper bound O(n log^{2} n) (relying on the computin g of the resultant [20], [27]) on the randomized complexity.

In the next two sections we give sketches of the proofs of theorems 1,2.

The construction from [5] of RCT with the linear complexity O(n) for the EQUALITY SET problem (which is the union of n-dimensional planes in 2n-dimensional space, see above) shows that the consideration just of hyperplanes in theorems 1,2 is crucial, and the nonlinear randomized complexity lower bounds cannot be directly extended to unions of planes of arbitrary dimensions.

In [3] deterministic computation trees with the branching signs {=, ≠} over algebraically closed fields of positive characteristics were considered, and the complexity lower bound Ω(log C) for recognizing an algebraic variety was established, where C is the degree of the Zeta-function of the variety. It is an open question to obtain non-linear complexity lower bounds for randomized computation trees over the fields of positive characteristics.

Let us also mention the paper [12] where a complexity lower bound was established for the randomized analytic decision trees (rather than for more customary algebraic ones) and also the paper [6] where a lower bound was ascertained for a randomized parallel computational model (rather than a sequential model considered in the quoted papers including the present one).

1 RCT over zero characteristic fields.

In this section we give a sketch of the proof of theorem 1 (the complete proof one can find in [7]).

Assume for the time being that the field F = F̄ is algebraically closed. Denote by N_{0} the number of 0-faces (in other words, vertices) of the arrangement S = H_{1} ∪ ⋯ ∪ H_{m}.

Similar to [27], [17] consider the graph of the gradient map of a polynomial 0 ≢ g ∈ F [X_{1}, …, X_{n}]

G = \{(x = (x_{1}, …, x_{n}), \frac{∂g}{∂X_{1}} (x), …, \frac{∂g}{∂X_{n}} (x))\} ⊂ F^{2n}

The main technical tool in the proof of theorem 1 is the following lower bound on the degree deg G (defined as the degree of the projective closure of G [23], [25]).

Lemma 1.1. deg G ≥ \frac{N_{0}}{2^{2n}}

Denote by C(g) the multiplicative complexity of g. The results from [27], [1] imply the inequality deg G ≤ 2^{3C(g)} which together with lemma 1.1 entail the following lower bound on the multiplicative complexity of g.

Proposition 1. If a polynomial 0 ≢ g ∈ F [X_{1}, …, X_{n}] vanishes on the arrangement S with N_{0} vertices then C(g) ≥ \frac{1}{3}(log_{2} N_{0} − 2n).

We remark that if N_{l} denotes the number of l-faces of S then one obtains the similar lower bound \frac{1}{3}(log_{2} N_{l} − 2(n − l)) by means of intersecting S with a (n − l)- dimensional plane.

Now let F be an arbitrary zero characteristic field. To complete the proof of theorem 1 observe that if RCT T = {T_{α}}_{α} recognizes S with an error probability γ < 1/2, then for every α CT T_{α} possesses the unique ”thick” path (from the root to a leaf), along which all the testing polynomials f_{1}, …, f_{k} ∈ F [X_{1}, …, X_{n}] have the branching sign ≠. One can prove that with a probability greater than 1−2γ > 0 the product f_{1} ⋯ f_{k} vanishes on at least q > \frac{1−2γ}{1+2γ} m of hyperplanes among H_{1}, …, H_{m}. Taking into account that γ could be made as close to zero as desired at the expense of increasing the depth of RCT by a suitable constant factor [19], we apply proposition 1 and the remark just after it to the polynomial f_{1} ⋯ f_{k} (notice that the multiplicative complexity of the latter product does not exceed 2k−1), and get a lower bound on k. Since the complexity of RCT under consideration is greater or equal to k, one completes the proof of theorem 1.

2 RCT over reals

In this section we give a sketch of the proof of theorem 2 (the complete proof one can find in [8]).

Again let F be a zero characteristic field and Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} be k-face of the arrangement S = H_{1} ∩ ⋯ ∩ H_{m}. Fix arbitrary coordinates Z_{1}, …, Z_{k} in Γ. Then treating H_{i_{1}}, …, H_{i_{n−k}} as the coordinate hyperplanes of the coordinates Y_{1}, …, Y_{n−k}, one gets the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} in F^{n}. The next construction of the leading terms of a polynomial is similar to [13], [11].

For any polynomial f(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}] following [13], [11] define its leading term

αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}

0 ≠ α ∈ F (with respect to the coordinate system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) as follows. First take the minimal integer m_{n−k} such that Y_{n−k}^{m_{n−k}} occurs in the terms of f = f^{(0)}. Consider the polynomial

0 ≢ f^{(1)} = (\frac{f}{Y_{n−k}^{m_{n−k}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}, 0)

∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}]

which could be viewed as a polynomial on the hyperplane H_{i_{n−k}}. Observe that m_{n−k} depends only on H_{i_{n−k}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}, since a linear transformation of the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1} changes the coefficients (being the polynomials from F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}]) of the expansion of f in the variable Y_{n−k}, and a coefficient vanishes identically if and only if it vanishes identically after the transformation. Then f^{(1)} is the coefficient of the expansion of f at the power Y_{n−k}^{m_{n−k}}.

Second, take the minimal integer m_{n−k−1} such that Y_{n−k−1}^{m_{n−k−1}} occurs in the terms of f^{(1)}. In other words, Y_{n−k−1}^{m_{n−k−1}} is the minimal power of Y_{n−k−1} occurring in the terms of f in which occurs the power Y_{n−k}^{m_{n−k}}. Therefore, m_{n−k}, m_{n−k−1} depend only on the hyperplanes H_{n−k}, H_{n−k−1} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}, since (as above) a linear transformation of the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2} changes the coefficients (being the polynomials from F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}]) of the expansion of f in the variables Y_{n−k}, Y_{n−k−1} and a coefficient vanishes identically if and only if it vanishes identically after the transformation. Denote by 0 ≢ f^{(2)} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}] the coefficient of the expansion of f at the monomial Y_{n−k−1}^{m_{n−k−1}} Y_{n−k}^{m_{n−k}}. Obviously

f^{(2)} = (\frac{f^{(1)}}{Y_{n−k−1}^{m_{n−k−1}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}, 0)

One could view f^{(2)} as a polynomial on the (n − 2)-

dimensional plane H_{i_{n−k}} ∩ H_{i_{n−k−1}}.

Continuing in the similar way, we obtain consecutively the (non-negative) integers m_{n−k}, m_{n−k−1}, …, m_{1} and the polynomials

0 ≢ f^{(l)} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l}]

1 ≤ l ≤ n−k, by induction on l. Herewith, Y_{n−k−l+1}^{m_{n−k−l+1}} is the minimal power of Y_{n−k−l+1} occurring in the terms of f, in which occurs the monomial Y_{n−k−l+2}^{m_{n−k−1+2}} ⋯ Y_{n−k}^{m_{n−k}} for each 1 ≤ l ≤ n − k. Notice that m_{n−k}, …, m_{n−k−l} depend only on the hyperplanes H_{i_{n−k}}, …, H_{i_{n−k−l}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}. Then f^{(l)} is the coefficient of the expansion of f at the monomial Y_{n−k−l+1}^{m_{n−k−l+1}} ⋯ Y_{n−k}^{m_{n−k}} and

f^{(l+1)} = (\frac{f^{(l)}}{Y_{n−k−l}^{m_{n−k−l}}} ) (Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}, 0)

Thus, f^{(l)} depends only on H_{i_{n−k}}, …, H_{i_{n−k−l}} and not on Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}. One could view f^{(l)} as a polynomial on the (n − l) dimensional plane H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{n−k−l+1}}. Continuing, we define also m′_{k}, …, m′_{1}.

Finally, the leading term lm(f) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}} is the minimal term of f in the lexicographical ordering with respect to the ordering Z_{1} > ⋯ > Z_{k} > Y_{1} > ⋯ > Y_{n−k}. The leading term lm(f^{(l)}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}} Y_{1}^{m_{1}} ⋯ Y_{n−k−l}^{m_{n−k−l}}, we refer to this equality as the maintenance property (see also [13], [11]).

From now on the construction and the definitions differ from the ones in [13], [11].

For any polynomial g ∈ F [X_{1}, …, X_{n}] one can rewrite it in the coordinates \overline{g}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) and expand \overline{g} = g_{s} +g_{s+1} +⋯+g_{s_{1}}, where g_{j} ∈ F [Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}], s ≤ j ≤ s_{1} is homogeneous with respect to the variables Y_{1}, …, Y_{n−k} of degree j and g_{s} = g_{s}^{(0)} ≢

0. Consider the leading term lm(g_{s}) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}} and denote by Var^{(Γ)}(g) = Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(g) the number of positive (in other words, nonzero) integers among m_{n−k}, …, m_{1}, note that s = m_{1} + ⋯ + m_{n−k}. As we have shown above Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(g) is independent from the coordinates Z_{1}, …, Z_{k} of Γ. Obviously, Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(g) coincides with the number of 1 ≤ l ≤ n − k such that Y_{n−k−l}|g_{s}^{(l)}, the latter condition is equivalent to that the variety {g_{s}^{(l)} = 0} ∩ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{n−k−l+1}} contains the plane H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{n−k−l+1}} ∩ H_{i_{n−k−l}} (being a hyperplane in H_{i_{n−k}} ∩⋯∩H_{i_{n−k−l+1}}).

It is convenient (see also [13], [11]) to reformulate the introduced concepts by means of infinitesimals in case of a real closed field F (see e.g. [18]). We say that an element ε transcendental over F is an infinitesimal (relative 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 [18]).

One could make the order in F̃ (ε) clearer by embedding it in the larger real closed field F ((ε^{1/∞})) of Puiseux series (cf. e.g. [16]). A nonzero Puiseux series has the form b = ∑_{i≥i_{0}} β_{i}ε^{i/δ}, where −∞ < i_{0} < ∞ is an integer, β_{i} ∈ F for every integer i; β_{i_{0}} ≠ 0 and the denominator of the rational exponents δ ≥ 1 is an integer. The order on F ((ε^{1/∞})) is defined as follows: sgn(b) = sgn(β_{i_{0}}). When i_{0} ≥ 1, then b is called an infinitesimal, when i_{0} ≤ −1, then b is called infinitely large. For any not infinitely large b we define its standard part st(b) = st_{ε}(b) ∈ F as follows: when i_{0} = 0, then st(b) = β_{i_{0}}, when i_{0} ≥ 1, then st(b) = 0. In the natural way we extend the standard part to the vectors from (F ((ε^{1/∞})))^{n} and further to subsets in this space.

Now let ε_{1} > ε_{2} ⋯ > ε_{n+1} > 0 be infinitesimals, where ε_{1} is an infinitesimal relative to IR; then ε_{i+1} is an infinitesimal relative to IR(ε_{1}, …, ε_{i}) for all 0 ≤ i ≤ n. Denote the real closed field IR_{i} = IR ˜ (ε_{1}, …, ε_{i}), in particular, IR_{0} = IR. For an element b ∈ IR_{n+1} for brevity denote the standard part st_{i}(b) = st_{ε_{i+1}}(st_{ε_{i+2}} ⋯ (st_{ε_{n+1}}(b) ⋯)) ∈ IR_{i} (provided that it is definable).

Also we will use the Tarski’s transfer principle [28]. Namely, for two real closed fields F_{1} ⊂ F_{2} a closed (so, without free variables) formula in the language of the first-order theory of F_{1} is true over F_{1} if and only if this formula is true over F_{2}.

An application of Tarski’s transfer principle is the concept of the completion. Let F_{1} ⊂ F_{2} be real closed fields and Ψ be a formula (with quantifiers and, perhaps, with n free variables) of the language of the first-order theory of the field F_{1}. Then Ψ determines a semialgebraic set V ⊂ F_{1}^{n}. The completion V^{(F_{2})} ⊂ F_{2}^{n} is a semialgebraic set determined by the same formula Ψ (obviously, V ⊂ V^{(F_{2})}).

One could easily see that for any point (z_{1}, …, z_{k}) ∈ IR_{k}^{k} and a polynomial g ∈ IR[X_{1}, …, X_{n}] such that g_{s}^{(n−k)}(z_{1}, …, z_{k}) ≠ 0 (we utilize the introduced above notations) the following equality for the signs

σ_{1}^{m_{1}} … σ_{n−k}^{m_{n−k}} sgn(g_{s}^{(n−k)}(z_{1}, …, z_{k})) =
sgn(\overline{g}(z_{1}, …, z_{k}, σ_{1}ε_{k+1}ε_{n+1}, …, σ_{n−k}ε_{n}ε_{n+1})) (1)

holds for any σ_{1}, …, σ_{n−k} ∈ {−1, 1}. For any 1 ≤ i ≤ n − k such that m_{i} = 0 (1) holds also for σ_{i} = 0, agreeing that 0^{0} = 1. Moreover, the following polynomial identity holds:

g_{s}^{(n−k)}(Z_{1}, …, Z_{k}) =

st_{k} (\frac{\overline{g}(Z_{1}, …, Z_{k}, ε_{k+1}ε_{n+1}, …, ε_{n}ε_{n+1})}{ε_{k+1}^{m_{1}} ⋯ ε_{n}^{m_{n−k}}ε_{n+1}^{s}})

Now let F be an algebraically closed field of zero characteristic. Take a certain 0 < η ≤ 1 (it will be specified later). We call k-face Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} of the arrangement S strongly singular (with respect to a polynomial g ∈ F [X_{1}, …, X_{n}]) if Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(g) ≥ η(n − k). Denote by N the number of strongly singular k-faces of S with respect to g (since g will be fixed for the time being, in the sequel we omit mentioning of g in this context).

The following lower bound on the degree of the graph G of the gradient map of g (see section 1) strengthens lemma 1.1, being the main technical tool in the proof of theorem 2.

Lemma 2.1 deg G ≥ Ω(N/(m^{(1−η)(n−k)}2^{4n}))

Similar to proposition 1 from section 1 this lemma implies the following proposition.

Proposition 2. Let a polynomial g ∈ F [X_{1}, …, X_{n}] have N strongly singular k-faces in an arrangement H_{1}∪ ⋯ ∪ H_{m} ⊂ F^{n}. Then the multiplicative complexity C(g) ≥ 1/3(log N − (n − k)(1 − η) log m − 4n− const).

For a family of polynomials f_{1}, …, f_{t} ∈ IR[X_{1}, …, X_{n}] we define Var^{(Γ)}(f_{1}, …, f_{t}) to be the number of the variables among Y_{1}, …, Y_{n−k} which occur in at least one of the leading terms lm(f_{1,s_{1}}), …, lm(f_{t,s_{t}}), where H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes of the coordinates Y_{1}, …, Y_{n−k}, respectively; \overline{f}_{j}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) = f_{j}(X_{1}, …, X_{n}) and \overline{f}_{j} = f_{j,s_{j}} + f_{j,s_{j}+1} + ⋯, herewith f_{j,l} is homogeneous with respect to the variables Y_{1}, …, Y_{n−k} of degree l and f_{j,s_{j}} ≢ 0, 1 ≤ j ≤ t. Because the expansion into the homogeneous components \overline{f}_{1} ⋯ \overline{f}_{t} = (f_{1,s_{1}} ⋯ f_{t,s_{t}}) + ⋯ starts with f_{1,s_{1}} ⋯ f_{t,s_{t}}, we have lm(f_{1,s_{1}} ⋯ f_{t,s_{t}}) = lm(f_{1,s_{1}}) ⋯ lm(f_{t,s_{t}}) and hence Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(f_{1} ⋯ f_{t}) = Var^{(Γ)}(f_{1} ⋯ f_{t}) = Var^{(Γ)}(f_{1}, ⋯, f_{t}).

For any CT T_{1} we denote by Var^{(Γ)}(T_{1}) = Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(T_{1}) the maximum of the Var^{(Γ)}(f_{1} ⋯ f_{t}) taken over all the paths of T_{1}, whose f_{1}, …, f_{t} are testing polynomials along the path.

The proof of the following ”local” (i.e. concerning a single face) lemma relies on the relation (1) and is similar to lemma 1 [13], [11], but differs from it due to the different definition of the leading term lm.

Lemma 2.2. Let T = {T_{α}} be an RCT recognizing

a) an arrangement S = ∪_{1≤i≤m}H_{i} such that Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} is k-face of S, or

b) a polyhedron S^{+} = ∩_{1≤i≤m}H_{i}^{+} such that Γ = ∩_{1≤j≤n−k}H_{i_{j}} is k-face of S^{+} with error probability γ < \frac{1}{2}. Then Var^{(H_{i_{1}} ,...,H_{i_{n−k}})}(T_{α}) ≥ (1 − 2γ)^{2}(n − k) forx a fraction of \frac{1−2γ}{2−2γ} of all T_{α}’s.

The following ”global” (i.e, concerning the set of all faces) lemma is similar to lemma 2 from [13], [11], but its proof is considerably simpler.

Lemma 2.3. Let S = S or S = S^{+} satisfy the conditions of the theorem 2. Assume that CT T′ for some constant η > 1−c, satisfies the inequality Var^{(Γ)}(T′) ≥ η(n − k) for at least M ≥ Ω(m^{c(n−k)}) of k-faces Γ of S. Then the depth t of T′ is greater than Ω(n log m).

Proof of lemma 2.3: To each k-face Γ of S satisfying the inequality Var^{(Γ)}(T′) ≥ η(n−k), we correspond a path in T′ with the testing polynomials f_{1}, …, f_{t_{0}} ∈ IR [X_{1}, …, X_{n}], t_{0} ≤ t such that Var^{(Γ)}(f_{1} ⋯ f_{t_{0}}) ≥ Var^{(Γ)}(T′) (in other words, Γ is strongly singular k-face for f_{1} ⋯ f_{t_{0}}, see section 1). Denote f = f_{1} ⋯ f_{t_{0}}.

Assume that 3^{t} ≤ O(m^{(η−1+c)(n−k)/2}), otherwise we are done. Then there exists a path of T′ (let us keep the notation f_{1}, …, f_{t_{0}} for the testing polynomials along this path) which corresponds to at least N = Ω(m^{(c−η+1)(n−k)/2}) of strongly singular k-faces Γ for f (because there are most 3^{t} paths in T′). Proposition 2 implies that the multiplicative complexity C(f) ≥ \frac{1}{3}((η − 1 + c)(n − k) log m − 4n − const). Obviously C(f) ≤ t + t_{0} − 1 ≤ 2t − 1 (cf. the proof of theorem 1 in section 1). Hence t ≥ Ω(n log m) that proves lemma 2.3.

Finally we show how to deduce the theorem 2 from lemmas 2.2 and 2.3. Consider RCT {T_{α}} recognizing S with error probability γ < \frac{1}{2}. Lemma 2.2 and counting imply the existence of T_{α_{0}} such that the inequality Var^{(Γ)}(T_{α_{0}}) ≥ (1 − 2γ)^{2}(n − k) is true for M = \frac{1−2γ}{2(1−γ)}Ω(m^{c(n−k)}) of k-faces Γ of S. Apply lemma 2.3 to CT T′ = T_{α_{0}} with η = (1 − 2γ)^{2}. Since the error probability γ could be made a positive constant as close to zero as desired at the expense of increasing by a constant factor the depth of RCT [19], take γ such that η > 1 − c. Then lemma 2.3 entails that t ≥ Ω(n log m), which proves theorem 2.

3 Deterministic computation trees

Treating a deterministic computation tree (CT) as a particular case of RCT one can release the restriction on s ubarrangements in theorem 1 and obtain the following result.

Corollary 1.3 If a CT (over a zero characteristic field) recognizes an arrangement with N faces (of all the dimensions ) then its depth exceeds Ω(log N).

For CT over reals in a similar way one can release the restriction on the number of faces in theorem 2.

Corollary 2.3 If a CT (over reals) recognizes either an arrangement or a polyhedron S with N faces (of all the d imensions) then its depth exceeds Ω(log N).

In case of an arrangement one could deduce corollary 2.3 from [2], in case of a polyhedron the corolla ry strengthens the result from [15].

Acknowledgement. I would like to thank Marek Karpinski for useful discussions.

References

[1] W. Baur, V. Strassen, The complexity of partial derivatives, Theor. Comput. Sci., Vol. 22, 1983, pp. 317–330

[2] M. Ben-Or, Lower bounds for algebraic computation trees, Proc. ACM Symp. Th. Comput., 1983, pp. 80–86

[3] M. Ben-Or, Algebraic computation trees in characteristic p > 0, Proc. IEEE Symp. Found. Comput.Sci., 1994, pp. 534–539.

[4] A. Bjorner, L. Lovasz, A. Yao, Linear decision trees: volume estimates and topological bounds, Proc. ACM Symp. Th.Comput. 1992, pp. 170–177.

[5] P. Buergisser, M. Karpinski, T. Lickteig, On randomized algebraic test complexity, J. Complexity, Vol. 9, 1993, pp. 231–251.

[6] D.Grigoriev, Nearly sharp complexity bounds for multiprocessor algebraic computations, J. Complexity, vol.13, 1997, pp.50–64.

[7] D.Grigoriev, Complexity lower bounds for randomized computation trees over algebraically closed fields, submitted to Computational Complexity

[8] D,Grigoriev, Randomized Complexity Lower Bounds for Arrangements and Polyhedra, to appear in Discrete and Computational Geometry

[9] 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

[10] 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

[11] D. Grigoriev, M. Karpinski, Randomized quadratic lower bound for knapsack, Proc. ACM Symp. Th. Comput., 1997, pp. 76–85

[12] Grigoriev, M. Karpinski, R. Smolensky, Randomization and the computational power of analytic and algebraic decision trees, to appear in Computational Complexity, 1997

[13] D. Grigoriev, M. Karpinski, F. Meyer auf der Heide, R. Smolensky, A lower bound for randomized algebraic decision trees, Proc ACM Symp. Th. Comput., 1996, pp. 612–619

[14] 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

[15] D. Grigoriev, M. Karpinski, N. Vorobjov, Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, J. Discrete and Computational Geometry, Vol. 17,2, 1997, pp. 191–215.

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

[17] T. Lickteig, On semialgebraic decision complexity, Preprint TR-0–052 ICSI, Berkeley, 1990.

[18] S. Lang, Algebra, Addison-Wesley, New York, 1965 [19] F. Meyer auf der Heide, Simulating probabilistic by

deterministic algebraic computation trees, Theor. Comput. Sci., Vol. 41, 1985, pp. 325–330.

[20] R. Moenck, A. Borodin, Fast modular transforms via division Proc. IEEE Symp. Switching and Automata Theory 1972 pp. 90–96

[21] J. Montana, L. Pardo, Lower bounds for arithmetic networks, Appl. Algebra in Eng. Commun. Comput., Vol. 4, 1993, pp. 1–24.

[22] J.Montana, J.Morais, L.Pardo, Lower bounds for arithmetic network II: sum of Betti numbers, Appl. Algebra in Eng. Commun. Comput., Vol. 7, 1996, pp. 41-51.

[23] D. Mumford, Algebraic geometry, Springer, 1976.

[24] U. Manber, M. Tompa, Probabilistic, Nondetemrinistic and Alternating Decision Trees, Proc. 14th ACM STOC, 1982, pp. 234–244

[25] I. R. Shafarevich, Basic algebraic geometry, V. 1 – Springer, 1994.

[26] M. Steele, A. Yao, Lower bounds for algebraic decision trees, J. Algorithms, Vol. 3, 1982, pp. 1–8.

[27] V. Strassen, Die Berechnungskomplexitaet von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., Vol. 20, 1973, pp. 238–251.

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

[29] A. Yao, Algebraic decision trees and Euler characteristic, Proc. IEEE Symp. Found. Comput. Sci., 1992, pp. 268–277.

[30] A. Yao, Decision tree complexity and Betti numbers, Proc. ACM Symp. Th. Comput., 1994, pp. 615–624.