Quadratic Randomized Lower Bound for the Knapsack Problem^{∗}

Dima Grigoriev ^{†}  Marek Karpinski ^{‡}

∗A preliminary version of this paper appears in [GK97] †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, and the International Computer Science Institute, Berkeley. Research partially done while visiting Dept. of Computer Science, Princeton University. Research supported by DFG Grant KA 673/4-1, and by the ESPRIT BR Grants 7097 and EC-US 030. Email: marek@cs.uni-bonn.de

Randomized Lower Bound  Page 2 Marek Karpinski  Email: marek@cs.uni-bonn.de

2

Abstract

We prove Ω(n^{2}) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is also the first nontrivial lower bound for randomized computation trees. The method of the proof depends crucially on the new technique for proving lower bounds on the border complexity of a polynomial which could be of independent interest.

0 Introduction

We prove for the first time nonlinear complexity lower bounds for randomized computation trees (RCT s) (see e.g. [MT82], [S83]) recognizing languages like unions of hyperplanes (i.e. linear arrangements) or intersections of halfspaces (polyhedra). As an application we prove a quadratic lower bound on RCT s solving the knapsack problem, or more general, the restricted integer programming.

Obtaining general lower bounds for randomized computations was an open question for a long time (see e.g. [M85a, b, c] and [KV88]). Only recently, a nonlinear lower bound was proven in [GKMS96] for a weaker model of randomized d-decision trees (d-RDT s), in which the testing polynomials have degrees at most d (for 2-dimensional case the lower bound was proven in [GK93] and for the generic arrangements a lower bound was proved in [GK94]). In particular, for d-RDT s in [GKMS96] the lower bound Ω(n log n) was proven for the Element Distinctness Problem (i.e. whether all the numbers x_{1}, …, x_{n} are pairwise distinct), and the lower bound Ω(n^{2}) was proved for the Knapsack problem. Usually, the bound d on the degree in d-RDT is small enough, and the main difficulty while considering RCT is that the degree of testing polynomials in principle could be exponential in the depth. Therefore, we develop in the present paper a new method for obtaining complexity lower bounds for RCT s.

The method developed in the present paper is not applicable to the element distinctness problem. In [BKL93], [GKMS96] a linear depth RCT was constructed for a similar problem (permutation problem) beating its deterministic Ω(n log n)^{2} lower bound [B83]). This example shows that the still open problem of complexity of an RCT for the element distinctness problem is quite delicate.

We also mention that a linear \frac{n}{4} lower bound for an RCT recognizing the arrangement ⋃_{1≤i≤n}{X_{i} = 0} or the “orthant” ⋂_{1≤i≤n}{X_{i} ≥ 0} was proved in [GKMS96]. For a stronger model of randomized analytic decision trees (RADT) a complexity upper bound O(log^{2} n) for testing ⋂_{1≤i≤n}{X_{i} ≥ 0} was proven in [GKS96] (for deterministic analytic decision trees the exact complexity bound n was proved in [R72], [MPR94]). Besides, in [GKS96] for RADT a sublinear lower bound Ω(n^{1/2}) was proved for the union of orthants ⋃{σ_{i}X_{i} ≥ 0, 1 ≤ i ≤ n} where σ_{i} ∈ {−1, 1} and the number of negative among σ_{i} is divided by a fixed q such that q ≠ 2^{s} for any s.

For deterministic models of the computation and decision trees several methods for obtaining complextity lower bounds were developed earlier. The “topological” methods based on the number of connected components ([SY82], [B83]), or more general, on the sum of Betti numbers ([BLY92], [Y94]), provide the lower bound Ω(n^{2}) for the knapsack problem and the lower bound Ω(n log n) for the distinctness or the permutation problem. The already mentioned example from [BKL93] shows that these “topological” bounds cannot be directly extended to RCT.

For testing a polyhedron (to which the topological methods are not applicable), the differential-geometric method (involving the curvature) for obtaining complextity lower bounds for deterministic computations was developped in [GKV96], which provides Ω(log N) lower bound for decision trees (see also [GKV95]) and Ω(log N/ log log N) for computation trees, where N is the number of all faces of the polyhedron.

We now briefly describe the content of the paper. In section 1 we introduce the notion of the border complexity, for the similar notations cf. [S90]

[B79] [BCLR79], of a polynomial and prove a lower bound on it which is of independent interest, in terms of the number of connected components.

In section 2 we prove the main theorem which provides a complexity lower bound for RCT testing an arrangement or a polyhedron. For that purpose we use some tools (in particular, the tree of flags) from [GKMS96], but the proof differs from the one in [GKMS96] since the degree of RCT s could be exponential as we already mentioned.

In section 3 as an application of the main theorem we give a complexity quadratic lower bound Ω(n^{2} log j) for RCT testing the Restricted Integer Programming

L_{n,j} = ⋃_{a ∈ {0,...,j−1}^{n}}{aX = 1}

(which is an arrangement consisting of j^{n} hyperplanes). Notice that for j = 2 this problem coincides with the Knapsack Problem. In particular, in section 3 we give a lower bound j^{Ω(n^{2})} on the number of faces of L_{n,j} (and thereby, on the number of the connected components of the complement of L_{n,j}, which was also ascertained in [YI65], [M85b], [GKMS96], and [DL78]). Moreover, in section 3 we provide a stronger lower bound on the number of faces of subarrangements of L_{n,j} (under a subarrangement we understand the restriction of a subset of hyperplanes from L_{n,j} on a face of L_{n,j}). The analogue of this bound for subarrangements of the distinctness problem is wrong, that is why we cannot get a nonlinear complexity lower bound for RCT, solving the distinctness problem.

In the last section 4 we state the complexity lower bound for the deterministic computation trees recognizing a polyhedron under less restrictive conditions than for the randomized computation trees as in the theorem from section 2.

1 Lower bound on the border complexity

We start now with the technical development leading to the crucial lower bound on the border complexity of a polynomial.

Let H_{1}, …, H_{n−k} ⊂ IR^{n} be hyperplanes such that their intersection Γ = H_{1} ∩ ⋯ ∩ H_{n−k} has the dimension dim Γ = k. Fix arbitrary coordinates Z_{1}, …, Z_{k} in Γ. Then treating H_{1}, …, H_{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 IR^{n}.

For any polynomial f ∈ IR[X_{1}, …, X_{n}] rewrite it in the coordinates \overline{f}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) and following [GKMS96], define its leading term

lm(f) = αZ_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}

0 ≠ α ∈ IR (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. Consider the polynomial

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

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

which could be viwed as a polynomial on the hyperplane H_{n−k}. Observe that m_{n−k} depends only on H_{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 IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}]) of the expansion of \overline{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 \overline{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 \overline{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 IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}]) of the expansion of \overline{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)} ∈ IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−2}] the coefficient of the expansion of \overline{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_{n−k} ∩ H_{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)} ∈ IR[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 \overline{f}, in which occurs the monomial Y_{n−k−l+2}^{m_{n−k−l+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_{n−k}, …, H_{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 \overline{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_{n−k}, …, H_{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_{n−k} ∩ ⋯ ∩ H_{n−k−l+1}. Continuing, we define

also mk^{′}, …, m1^{′}.

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 \overline{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 [GKMS96]).

Denote by V ar(f) = V ar^{(H_{1},...,H_{n−k})} (f) the number of positive (i.e. nonzero) integers among m_{n−k}, …, m_{1}. As we have shown above, V ar(f) is independent from the coordinates Z_{1}, …, Z_{k} of Γ. Obviously, V ar(f) coincides with the number of 1 ≤ l ≤ n − k such that Y_{n−k−l} | f^{(l)}, the latter condition is equivalent to that the variety {f^{(l)} = 0} ⋂(H_{n−k} ∩⋯∩H_{n−k−l+1}) contains the plane H_{n−k} ∩ ⋯ ∩ H_{n−k−l+1} ∩ H_{n−k−l} (being a hyperplane in H_{n−k} ∩ ⋯ ∩ H_{n−k−l+1}).

It is convenient (see also [GKMS96]) to reformulate the introduced concepts by means of infinitesimals. Namely for a real closed field F (see e.g. [L65]) 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 [L65]).

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. [GV88]). 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+2} > 0 be infinitesimals, where ε_{1} is an infinitesimal relative to IR; in general ε_{i+1} is an infinitesimal relative to IR(ε_{1}, …, ε_{i}) for all 0 ≤ i ≤ n + 1. Denote the real closed field IR_{i} = ĨR(ε_{1}, …, ε_{i}), in particular, IR_{0} = IR. For an element b ∈ IR_{n+2} for brevity denote the standard part st_{i}(b) = st_{ε_{i+1}}(st_{ε_{i+2}} ⋯ (st_{ε_{n+2}}(b) ⋯) ∈ IR_{i} (provided that it is definable).

Also we will use the Tarski’s transfer principle [T51]. 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}.

Tarski’s transfer principle implies that a semialgebraic set {f_{1} ≥ 0, …, f_{k_{1}} ≥ 0, f_{k_{1}+1} > 0, …, f_{k} > 0} ⊂ F^{n}, where the polynomials f_{i} ∈ F [X_{1}, …, X_{n}] have the degrees deg(f_{i}) ≤ d, has at most (min\{2^{k}, (\frac{k}{n})^{n}\}d^{n})^{O(1)} connected components (cf. [GV88]), relying on this bound in case F = IR from [W68] (cf. also [BPR94]), which strenghtens the result of [M64].

Another 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 firstorder 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})}). Tarski’s transfer principle entails, in particular, that the number of connected components of V is the same as the one of V^{(F_{2})} (cf. [GV88]).

One could easily see that for any point (z_{1}, …, z_{k}) ∈ IR_{k+2}^{k} such that f^{(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 (f^{(n−k)}(z_{1}, …, z_{k})) =

sgn (\overline{f}(z_{1}, …, z_{k}, σ_{1}ε_{k+3}, …, σ_{n−k}ε_{n+2})) (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:

f^{(n−k)}(Z_{1}, …, Z_{k}) = st_{k+2} (\frac{\overline{f}(Z_{1}, …, Z_{k}, ε_{k+3}, …, ε_{n+2})}{ε_{k+3}^{m_{1}} ⋯ ε_{n+2}^{m_{n−k}}})  (2)

For a family of hyperplanes H_{1}, …, H_{m} ⊂ IR^{n} let S = ∪_{1≤i≤m}H_{i} be an arrangement, by B_{0} (H_{1}, …, H_{m}) we denote the number of connected components of the complement IR^{n} − S.

Following e.g. [S90] we define the complexity s = C(f) of a polynomial f ∈ IR[X_{1}, …, X_{n}] as the length of the shortest straight-line program which computes f. Recall that the latter is a sequence of operations u_{1} = X_{1}, …, u_{n} = X_{n}, then for every n < j ≤ s + n u_{j} = ũ_{j_{1}} ⊙ ũ_{j_{2}}, where for each i = 1, 2 either ũ_{j_{i}} = u_{j_{i}} with j_{i} < j or ũ_{j_{i}} ∈ IR and either ⊙ = × or ⊙ = +. To every u_{j} by recursion on j one attaches in the natural way a polynomial U_{j} ∈ IR[X_{1}, …, X_{n}] (the value of u_{j}). The straight-line program computes f if U_{s+n} = f.

Observe that one could consider also the division ⊙ = / and the resulting rational functions, but since we deal only with the signs of the testing functions in the computation trees (see below), we could consider separately the computations of the numerators and denominators of the rational functions by means of the straight-line programs without the divisions.

For a polynomial g ∈ IR[Z_{1}, …, Z_{k}] its border complexity \overline{C}(g) (cf. [S90]) is the minimal C(f) where f ∈ IR[X_{1}, …, X_{n}] for a certain n ≥ k such that g = f^{(n−k)}, for suitable coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}, which we treat as the linear forms in X_{1}, …, X_{n}. Actually, one could literally extend the concept of the border complexity to the polynomials with the coefficients from an arbitrary field.

The main result of this section is the following lower bound on the border complexity.

Proposition: Let for a polynomial g ∈ IR[Z_{1}, …, Z_{k}] its border complexity \overline{C}(g) ≤ s. Assume that H_{1}, …, H_{m} ⊂ IR^{k} are pairwise distinct hyperplanes such that the corresponding linear functions L_{H_{i}} | g, 1 ≤ i ≤ m (where the zero set of L_{H_{i}} is H_{i}). Then B_{0}(H_{1}, …, H_{m}) ≤ 2^{O(s+k)}.

Remark: In fact, one could formulate the proposition in a stronger setting as follows (the proof goes through literally). For a polynomial g with the border complexity less than s, the number of the connected components in the complement in IR^{k} of the set {g = 0} of zeroes of g does not exceed 2^{O(s+k)}.

Proof: Let u_{i} = X_{i}, 1 ≤ i ≤ n; u_{j} = ũ_{j_{1}} ⊙ ũ_{j_{2}}, n + 1 ≤ j ≤ n + s be a straight-line program which computes a certain polynomial f ∈ IR[X_{1}, …, X_{n}] such that g = f^{(n−k)} for suitable coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} (we utilize the introduced above notations). Express X_{i} = α_{1}^{(i)}Z_{1} + ⋯ + α_{k}^{(i)}Z_{k} + β_{1}^{(i)}Y_{1} + ⋯ β_{n−k}^{(i)}Y_{n−k}, 1 ≤ i ≤ n, where α_{j}^{(i)}, β_{j}^{(i)} ∈ IR. Remind that by \overline{f}(Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) we denote the polynomial f in the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}.

Due to (2) for any point (z_{1}, …, z_{k}) ∈ IR_{2}^{k} we have

g(z_{1}, …, z_{k}) = st_{2} (\frac{\overline{f}(z_{1}, …, z_{k}, ε_{k+3}, …, ε_{n+2})}{ε_{k+3}^{m_{1}} ⋯ ε_{n+2}^{m_{n−k}}})  (3)

Denote u′_{i} = α_{1}^{(i)}z_{1} + ⋯ + α_{k}^{(i)}z_{k} + β_{1}^{(i)}ε_{k+3} + ⋯ + β_{n−k}^{(i)}ε_{n+2}, 1 ≤ i ≤ n. Introduce a new variable Z_{0} and two semialgebraic sets

V = { (z_{0}, z_{1}, …, z_{k}, u_{n+1}, …, u_{n+s}) ∈ IR_{n+2}^{k+s+1} :

u_{j} = ũ′_{j_{1}} ⊙ ũ′_{j_{2}}, n + 1 ≤ j ≤ n + s, where for each i = 1, 2 either ũ′_{j_{i}} = u′_{j_{i}} when 1 ≤ j_{i} ≤ n and ũ′_{j_{i}} = u_{j_{i}} when n < j_{i} < j, or ũ′_{j_{i}} ∈ IR according to the straight-line program which computes f;

((\frac{u_{n+s}}{ε_{k+3}^{m_{1}} ⋯ ε_{n+2}^{m_{n−k}}})^{2} − ε_{1})^{2} +

(z_{0}^{2} + z_{1}^{2} + ⋯ + z_{k}^{2} − \frac{1}{ε_{1}} )^{2} < ε_{2} \};

V = \{(z_{0}, z_{1}, …, z_{k}) ∈ IR_{1}^{k+1} : g^{2} (z_{1}, …, z_{k}) = ε_{1}; z_{0}^{2} + z_{1}^{2} + ⋯ + z_{k}^{2} = \frac{1}{ε_{1}} \}

Denote by ∏ : IR_{n+2}^{k+s+1} → IR_{n+2}^{k+1} the linear projection along the coordinates u_{n+1}, …, u_{n+s}. The linear projection ∏ : V ˜→ ∏(V) is an isomorphism of the semialgebraic sets, since the projection

∏(V) = \{(z_{0}, z_{1}, …, z_{k}) ∈ IR_{n+2}^{k+1} : ((\frac{\overline{f}(z_{1}, …, z_{k}, ε_{k+3}, …, ε_{n+2})}{ε_{k+3}^{m_{1}} ⋯ ε_{n+2}^{m_{n−k}}})^{2} − ε_{1})^{2} +

(z_{0}^{2} + z_{1}^{2} + ⋯ + z_{k}^{2} − \frac{1}{ε_{1}} )^{2} < ε_{2}\}

and the inverse mapping is given by the polynomial mapping u_{j} = ũ′_{j_{1}} ⊙ ũ′_{j_{2}}, n + 1 ≤ j ≤ n + s.

Then V ⊂ ∏(V) because of (3).

Furthermore, st_{1}(∏(V)) = V; the left side is definable since for any point (z_{0}, …, z_{k}) ∈ ∏(V) the square of its euclidean norm ∥z_{o}, …, z_{k}∥^{2} = z_{0}^{2} + ⋯ + z_{k}^{2} < \frac{1}{ε_{1}} + ε2^{\frac{1}{2}} < \frac{1}{ε_{1}} + 1. By the same reason lemma 1 from [GV88] states that the number N_{3} of the connected components of V does not exceed the number N_{4} of the connected components of ∏(V), the latter coincides with the number of the connected components of V since it is isomorphic to ∏(V).

We claim that for any connected component W ⊂ IR^{k} (which is an open set in the euclidean topology) of the component IR^{k}−{g = 0} and an arbitrary point w_{0} ∈ ∂W on the boundary, there exists a point (z_{1}, …, z_{k}) ∈ W^{(IR_{1})} ⊂ IR_{1}^{k} from the completion W^{(IR_{1})} (as we have seen above from Tarski’s transfer principle, the connected components W of the complement are in the bijective correspondence with their completions W^{(IR_{1})} ⊃ W, being the connected components of the complement {g = 0}^{(IR_{1})} in IR_{1}^{k}, the number of these connected components we denote by N_{0}) such that g^{2}(z_{1}, …, z_{k}) = ε_{1} and st_{0}(z_{1}, …, z_{k}) = w_{0} (cf. lemma 3 from [GV88]). Indeed, pick out an arbitrary point w ∈ W. Taking into account that w_{0} ∈ ∂(W^{(IR_{1})}), so g(w_{0}) = 0, and 0 < g^{2}(w) ∈ IR we conclude that g^{2} attains on W^{(IR_{1})} any intermediate value from IR_{1} between 0 and g^{2}(w) (using Tarski’s transfer principle), in particular, ε_{1}. Now take a point w_{1} ∈ W^{(IR_{1})} being the nearest to w_{0} such that g^{2}(w_{1}) = ε_{1} (its existence follows again from Tarski’s transfer principle). It suffices to prove that st_{0}(w_{1}) = w_{0}. Suppose the contrary. Then there exists 0 < r ∈ IR such that for any point w_{2} ∈ W^{(IR_{1})} with the distance ∥w_{0} − w_{2}∥ ≤ r the inequality g^{2}(w_{2}) < ε_{1} holds. Since w_{0} ∈ ∂W there exists a point w_{3} ∈ W such that ∥w_{0} − w_{3}∥ ≤ r, then 0 < g^{2}(w_{3}) ∈ IR and we get a contradiction with the supposition, and that proves the claim.

Furthermore, since w_{0} ∈ IR^{k} and st_{0}(z_{1}, …, z_{k}) = w_{0}, there exists 0 < r_{1} ∈ IR such that the norm ∥z_{1}, …, z_{k}∥ ≤ r_{1}, a fortiori ∥z_{1}, …, z_{k}∥^{2} ≤ \frac{1}{ε_{1}} .

Consider a semialgebraic set

V_{0} = {(z_{1}, …, z_{k}) ∈ IR_{1}^{k} : g^{2} (z_{1}, …, z_{k}) = ε_{1}}

Denote by N_{1} the number of the connected components of V_{0} containing a point w_{4} with the square of the euclidean norm ∥w_{4}∥^{2} ≤ \frac{1}{ε_{1}} . The proved above claim states that the number N_{0} does not exceed N_{1}, taking into account that

V_{0} ⊂ (IR^{k} − {g = 0})^{(IR_{1})} = IR_{1}^{k} − ({g = 0})^{(IR_{1})}

On the other hand, B_{0}(H_{1}, …, H_{m}) ≤ N_{0}, since ⊓_{1≤i≤m}L_{H_{i}} | g (evidently, in every connected component, being an open set in the euclidean topology, of the complement of the arrangement (IR^{k} − ⋃_{1≤i≤m} H_{i}) ⊃ (IR^{k} − {g = 0}), there exists a point at which g does not vanish).

Obviously, N_{1} is less than or equal to the number N_{2} of the connected components of the set

V_{1} = V_{0} ∩ \{(z_{1}, …, z_{k}) ∈ IR_{1}^{k} : ∥z_{1}, …, z_{k}∥^{2} ≤ \frac{1}{ε_{1}} \}

In its turn V_{1} = ∏_{0}(V), where ∏_{0} : IR_{1}^{k+1} → IR_{1}^{k} is the projection along the coordinate Z_{0}. Hence N_{2} ≤ N_{3}.

Gathering the obtained chain of inequalities B_{0}(H_{1}, …, H_{m}) ≤ N_{0} ≤ N_{1} ≤ N_{2} ≤ N_{3} ≤ N_{4} for the numbers of the connected components, we conclude that B_{0}(H_{1}, …, H_{m}) does not exceed the number of connected components of V. The latter is less than 2^{O(s+k)} according to [W68] and Tarski’s transfer principle (see above).

The proposition is proved.

2 Lower bounds for randomized computation

trees

Recall (see e.g. [B83]) that in the computation tree (CT) testing polynomials are computed along paths using the elementary arithmetic operations.

In particular, for a testing polynomial f_{i} ∈ IR[X_{1}, …, X_{n}] at the level i (assuming that the root has the zero level) we have C(f_{i}) ≤ i. Under RCT (cf. [MT82], [S83], [M85a,b,c]) we mean a collection of CT T = {T_{α}} and a probabilistic vector p_{α} ≥ 0, ∑_{α} p_{α} = 1 such that T_{α} is chosen with the probability p_{α}. The main requirement is that for any input RCT gives a correct output with the probability 1 − γ > \frac{1}{2} (γ is called the error probability of RCT).

For a hyperplane H ⊂ IR^{n} by H^{+} ⊂ IR^{n} denote the closed halfspace {L_{H} ≥ 0}, where L_{H} is a certain linear function with the zero set H. For a family of hyperplanes H_{1}, …, H_{m} the intersections S^{+} = ∩_{1≤i≤m}H_{i}^{+} is called a polyhedron. An intersection Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}} is called k-face of S^{+} if dim Γ = dim(Γ ∩ S^{+}) = k. By ϕ_{k}(S^{+}) we denote the number of k-faces of S^{+}. Similary (and even simpler) for the arrangement S = ∪_{1≤i≤m}H_{i} its k-face is any k-dimensional intersection of the form Γ = H_{i_{1}} ∩ ⋯ ∩ H_{i_{n−k}}. By ϕ_{k}(S) we denote the number of k-faces of S.

Now we are able to formulate the main result of this paper.

Theorem: Let there exist positive constants c_{1}, c_{2}, c_{3}, c_{4} such that c_{3}(1− c_{1}) < c_{2} and an arrangement S = S = ∪_{1≤i≤m}H_{i} or a polyhedron S = S^{+} = ∩_{1≤i≤m}H_{i}^{+} satisfy the following properties:

1. ϕ_{[c_{1}n]}(S) ≥ Ω(m^{c_{2}n});

2. for any k-face Γ of S with k ≥ c_{1}n and any subfamily H_{i_{1}}, …, H_{i_{q}} of H_{1}, …, H_{m} with at least q ≥ m^{c_{3}} hyperplanes such that H_{i_{j}} ⊅ Γ for each 1 ≤ j ≤ q and the hyperplanes H_{i_{1}} ∩ Γ, …, H_{i_{q}} ∩ Γ in Γ are pairwise distinct, the number of the connected components B_{0}^{(Γ)}(H_{i_{1}} ∩ Γ, …, H_{i_{q}} ∩Γ) of the complement in Γ of the arrangement ∪_{1≤j≤q}(H_{i_{j}} ∩ Γ) is greater than Ω(m^{c_{4}n}).

Then for any RCT recognizing S, its depth is greater than Ω(n log m). Before proceeding to the proof of the theorem, we need some preparation. First we fix the canonical representation of k-face Γ in two cases: namely,

of S and of S^{+}, respectively (see [GKMS96]). In the case of S take the maximal i_{n−k} ≤ m such that H_{i_{n−k}} ⊃ Γ, then the maximal i_{n−k−1} such that H_{i_{n−k−1}} ⊃ Γ and dim(H_{i_{n−k}} ∩ H_{i_{n−k−1}}) = n − 2 (obviously i_{n−k−1} < i_{n−k}) and so on we produce the indices i_{n−k} > i_{n−k−1} > ⋯ > i_{1} such that Γ = H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{1}}. As the representation of Γ we take the flag of planes: H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ ⋯ ⊃ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{1}} = Γ.

Now consider the case of S^{+}. W.l.o.g. one could assume that dim S^{+} = n. Under a hyperplane of a l-dimensional polyhedron we mean a (l − 1)-plane which is (l − 1)-face of the polyhedron. W.l.o.g. one could assume that all hyperplanes H_{1}, …, H_{m} are hyperfaces of S^{+}.

Take the maximal i_{n−k} ≤ m such that H_{i_{n−k}} ⊃ Γ. Denote the polyhedron S_{1}^{+} = H_{i_{n−k}}∩S^{+}. Obviously, Γ is its k-face and dim S_{1}^{+} = n−1. By H_{1} denote the family of all hyperplanes H_{i} such that H_{i} ⊃ Γ and (H_{i_{n−k}} ∩H_{i}) is a hyperface of S_{1}^{+} (thereby, it is (n − 2)-face of S^{+}). Then H_{1} ⊂ {H_{1}, …, H_{i_{n−k}−1}} because of the choice of i_{n−k}. Since S_{1}^{+} is a convex polyhedron, any of its faces is an intersection of some of its hyperfaces, in particular, any of its face Γ_{1} which contains Γ ⊂ Γ_{1}, could be represented as Γ_{1} = H_{i_{n−k}} ∩ (⋂_{H_{i}∈H′_{1}} H_{i}) for a suitable subfamily H1^{′} ⊂ H_{1}.

Assume that by recursion on l it is already produced a sequence of indices i_{n−k} > ⋯ > i_{n−k−l+1}, 1 ≤ 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 1 ≤ l_{1} ≤ l. Denote Γ^{(l)} = H_{i_{n−k}}∩⋯∩H_{i_{n−k−l+1}} and the polyhedron S_{l}^{+} = Γ^{(l)} ∩ 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} Γ^{(l)} ∩ H_{i} contains Γ and is a hyperface of S_{l}^{+}, and vice versa any hyperface of S_{l}^{+} has the form Γ^{(l)} ∩ H_{i} for a certain H_{i} ∈ H_{l}. Hence any face Γ_{1} ⊃ Γ of S_{l}^{+} has the form Γ_{1} = Γ^{(l)} ∩ (⋂_{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+1)} = Γ^{(l)} ∩ H_{i_{n−k−l}} is a hyperface of S_{l}^{+} (and thereby is (n−l−1)-face of S^{+}). 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+1)}∩H_{i} is a hyperface of S_{l+1}^{+} (evidently, Γ^{(l+1)}∩H_{i} ⊃ Γ 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 Γ_{2} of S_{l+1}^{+} such that Γ_{2} ⊃ Γ, there exists H_{i} ∈ H_{l+1} for which Γ_{2} = Γ^{(l+1)} ∩ H_{i}. According to the property of H_{l} there exist H_{j_{1}}, H_{j_{2}} ∈ H_{l} such that Γ_{2} = Γ^{(l)} ∩ H_{j_{1}} ∩ H_{j_{2}}. Since Γ^{(l+1)} ⊃ Γ_{2} and dim Γ^{(l+1)} = dim Γ_{2} + 1 = n − l − 1, either Γ_{2} = Γ^{(l+1)} ∩ H_{j_{1}} or Γ_{2} = Γ^{(l+1)} ∩ H_{j_{2}} is valid. In the former case H_{j_{1}} ∈ H_{l+1}, in the latter case H_{j_{2}} ∈ H_{l+1}. This completes the recursive step.

Thus, at the end of recursion we obtain a flag, which we treat as the claimed canonical representation of the k-face Γ:

H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ ⋯ ⊃ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{1}} = Γ

such that for each 1 ≤ l ≤ 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).

Fix k-face Γ of S, where either S = S or S = S^{+}. Let H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ ⋯ ⊃ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{1}} = Γ be a flag which represents Γ as described above. For a family of polynomials f_{1}, …, f_{s} ∈ IR[X_{1}, …, X_{n}] we define V ar^{(Γ)}(f_{1}, …, f_{s}) to be the number of the variables among Y_{1}, …, Y_{n−k} (we utilize the notations introduced in section 1) which occur in at least one of lm(f_{1}), …, lm(f_{s}), where H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes of the coordinates Y_{1}, …, Y_{n−k}, respectively. Since lm(f_{1} ⋯ f_{s}) = lm(f_{1}) ⋯ lm(f_{s}) we get that V ar^{(H_{i_{1}},...,H_{i_{n−k}})}(f_{1} ⋯ f_{s}) = V ar^{(Γ)}(f_{1} ⋯ f_{s}) = V ar^{(Γ)}(f_{1}, …, f_{s}).

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

The following lemma was proved in [GKMS96].

Lemma 1: Let T = {T_{α}} be an RCT recognizing

a) an arrangement S = ∪_{1≤i≤m}H_{i} such that Γ = ∩_{1≤j≤n−k}H_{i_{j}} is k-face of S, or b) a polyhedron S^{+} = ∩_{1≤i≤m}H_{i}^{+} such that for each 1 ≤ l ≤ n − k

∩_{l≤j≤n−k}H_{i_{j}} is (k + l − 1)-face of S^{+} (denote Γ = ∩_{1≤j≤n−k}H_{i_{j}})

with error probability γ < \frac{1}{2}. Then V ar^{(H_{i_{1}},...,H_{i_{n−k}})}(T_{α}) ≥ (1−2γ)^{2}(n− k) for a fraction of \frac{1−2γ}{2−2γ} of all T_{α}’s.

Remark: Notice that the conditions in a), b) are fulfilled if H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ ⋯ ⊃ H_{i_{n−k}} ∩ ⋯ ∩ H_{i_{1}} = Γ is the canonical flag representation of Γ in both cases of S and S^{+} (see above).

Proof of Lemma 1: Choose the coordinates Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} such that Z_{1}, …, Z_{k} are the coordinates in Γ and H_{i_{1}}, …, H_{i_{n−k}} are the coordinate hyperplanes of Y_{1}, …, Y_{n−k}, respectively (cf. section 1), which satisfy the following properties. The origin \underbrace{(0, …, 0)}_{n} of this coordinates

system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k} does not lie in any l-face with l < k and besides, in the case b) (0, …, 0) belongs to the polyhedron S^{+}. Also we require that for any testing polynomial f from any CT T_{α} f^{(n−k)} \underbrace{(0, …, 0)}_{k} ≠

0 holds (recall that f^{(n−k)} ≢ 0 depends only on H_{i_{1}}, …, H_{i_{n−k}}, see section 1).

a) Consider the point E = (\underbrace{0, …, 0}_{k}, ε_{k+3}, …, ε_{n+2}) and the points

E_{i}^{(0)} = (\underbrace{0, …, 0}_{k}, ε_{k+3}, …, ε_{k+i+1}, 0, ε_{k+i+3}, …, ε_{n+2}), 1 ≤ i ≤ n − k. Then

the point E ∉ S (because of the choice of the origin of the coordinates system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}) and E_{i}^{(0)} ∈ S, 1 ≤ i ≤ n − k.

Easy counting yields that there is a fraction of \frac{1−2γ}{2(1−γ)} of all T_{α}’s that give the correct outputs for E and for at least (1 − 2γ)^{2}(n − k) many among E_{i}^{(0)}, 1 ≤ i ≤ n − k. Take such T_{α_{0}} and some 1 ≤ i_{0} ≤ n − k for which T_{α_{0}} gives the correct output.

Denote by f_{1}, …, f_{s} the testing polynomials along the path in T_{α_{0}} followed by the input E. We claim that Y_{i_{0}} occurs in one of the leading terms lm(f_{1}), …, lm(f_{s}) (thereby, Y_{i_{0}} occurs in lm(f_{1} ⋯ f_{s}) = lm(f_{1}) ⋯ lm(f_{s}), see above).

Suppose the contrary. Let lm(f_{l}) = Z_{1}^{m′_{1}} ⋯ Z_{k}^{m′_{k}}Y_{1}^{m_{1}} ⋯ Y_{n−k}^{m_{n−k}}, then m_{i_{0}} = 0 by the supposition. Then (1) from section 1 implies that sgn(f_{l}(E_{i_{0}}^{(0)})) = sgn(f_{l}^{(n−k)}(\underbrace{0, …, 0}_{k})) ≠ 0 because of the choice of the ori-

gin of the coordinates system Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k}. By the same token sgn(f_{l}(E)) = sgn(f_{l}^{(n−k)}(\underbrace{0, …, 0}_{k})). Therefore, E_{i_{0}}^{(0)} satisfies all the tests

along the path under consideration in T_{α_{0}} followed by the input E, hence the output of T_{α_{0}} for the input E_{i_{0}}^{(0)} is the same as for the input E, so incorrect, that contradicts the choice of i_{0}.

b) First we show that E ∈ S^{+}. Take any hyperplane H_{l} = {κ_{1}Z_{1} + … + κ_{k}Z_{k} + β_{1}Y_{1} + … + β_{n−k}Y_{n−k} + β_{0} = 0}, 1 ≤ l ≤ m given by a linear function L_{H_{l}} with the coefficients κ_{i}, β_{j} ∈ IR. We need to show that L_{H_{l}}(E) ≥ 0. Let 0 ≤ j_{0} ≤ n − k be the uniquely defined index such that β_{0} = … = β_{j_{0}−1} = 0, β_{j_{0}} ≠ 0 (if all β_{0} = … = β_{n−k} = 0 then L_{H_{l}}(E) = 0). We prove 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}} = (\underbrace{0, …, 0}_{k}, y_{1}^{(n−j_{0})}, …, y_{j_{0}}^{(n−j_{0})}, 0, …, 0) ∈

((H_{i_{n}} ∩ … ∩ H_{i_{j_{0}+1}}) ∩ S^{+}) − H_{i_{j_{0}}}. Then y_{j_{0}}^{(n−j_{0})} ≠ 0, therefore y_{j_{0}}^{(n−j_{0})} > 0 since v_{n−j_{0}} ∈ S^{+}. Hence 0 < sgn L_{H_{l}}(v_{n−j_{0}}) = sgn(β_{j_{0}} · y_{j_{0}}^{(n−j_{0})}), this implies that sgn(β_{j_{0}}) > 0. Thus E ∈ S^{+}.

Notice that the points E_{i}^{(+)} = (0, …, 0, ε_{k+3}, …, ε_{k+i+1}, −ε_{k+i+2}, ε_{k+i+3}, …, ε_{n+2}) ∉ S^{+}, 1 ≤ i ≤ n − k.

The rest of the proof is similar as in a), with replacing the role of the points E_{i}^{(0)} by E_{i}^{(+)}. In a similar way if m_{i_{0}} = 0 then sgn(f_{l}(E_{i_{0}}^{(+)})) = sgn(f_{l}^{(n−k)}(\underbrace{0, …, 0}_{k})) = sgn(f_{l}(E)) ≠ 0 again because of (1) from section 1.

Lemma 1 is proved.

An analogue of lemma 2 from [GKMS96] is the following lemma.

Lemma 2: Let S = S or S = S^{+} satisfy the condition 2. of the theorem. Assume that CT T′ for some constant c > 0, satisfies the inequality V ar^{(Γ)}(T′) ≥ c(1 − c_{1})n for at least M ⌈c_{1}n⌉-faces Γ of S. Then the depth t of T′ fulfils either t ≥ Ω(n log m) or M ≤ O(3^{t}m^{(1−c+c_{3}+δ)(1−c_{1})n}), where a constant δ > 0 could be made as close to zero as desired.

The proof of lemma 2 differs from the proof of the analogous lemma 2 from [GKMS96] proved for d-decision trees, in which the degrees of the testing polynomials do not exceed d, rather than computation trees (considered in the present paper), in which the degrees of the testing polynomials could be exponential in the depth t of CT. Therefore the main tool in the proof of lemma 2 is the lower bound on the border complexity from the proposition (see section 1).

Before proving lemma 2 we show how to deduce the theorem from lemmas 1 and 2. Consider RCT \{T_{α}\} recognizing S with error probability γ < \frac{1}{2}. Denote k = ⌈c_{1}n⌉. Lemma 1, condition 1. of the theorem and counting imply the existence of T_{α_{0}} such that the inequality V ar^{(Γ)}(T_{α_{0}}) ≥ (1−2γ)^{2}(n−k) is true for M = \frac{1−2γ}{2(1−γ)}Ω(m^{c_{2}n}) k-faces Γ of S. Apply lemma 2 to CT T′ = T_{α_{0}} with c = (1 − 2γ)^{2}. If t ≥ Ω(n log m) the theorem is proved, else since the error probability γ could be made a positive constant as close to zero as desired at the expence of increasing by a constant factor the depth of RCT [M85a,c], take γ such that (1 − c + δ) < \frac{c_{2}−c_{3}(1−c_{1})}{1−c_{1}}. Then lemma 2 entails that t ≥ Ω(n log m), which proves the theorem. Thus, it remains to prove lemma 2.

Proof of lemma 2: To each k-face Γ of S satisfying the inequality V ar^{(Γ)}(T′) ≥ c(n − k), we correspond a path in T′ with the testing polynomials f_{1}, …, f_{s} ∈ IR[X_{1}, …, X_{n}] such that V ar^{(Γ)}(f_{1} ⋯ f_{s}) ≥ V ar^{(Γ)}(T′). Denote f = f_{1} ⋯ f_{s}. Consider a canonical representation of Γ by a flag (see above)

H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ … ⊃ H_{i_{n−k}} ∩ … ∩ H_{i_{1}} = Γ

Fix this path of T′ for the time being and consider all k-faces Γ to which corresponds this path. We arrange the representing flags of all these k-faces in a tree T which we call the tree of flags (cf. the proof of lemma 2 from [GKMS96]). T has a root with the zero level, each its path has the same length n − k (such trees are called regular), some of its vertices are labeled.

We construct T by induction on the level of its vertices. The base of induction. For each k-face Γ to which corresponds the fixed path of T′, construct a vertex, being a son of the root of T , and to this vertex (of level 1) attach the hyperplane H_{i_{n−k}} (we utilize inroduced above notations). Thus, to different sons of the root different hyperplanes are attached. We label the constructed vertex if and only if Y_{n−k}|f (the latter means that the linear function or the variable Y_{n−k} gives a contribution into V ar^{(Γ)}(f)). Besides, we assign to the constructed vertex the polynomial f^{(1)} ∈ IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−1}] (see section 1).

Now assume by induction on l that l < n − k levels of T are already constructed. Consider any vertex v of T at l-th level. To the vertex v leads the partially labeled path (from the root), to whose vertices the beginning elements of a flag are attached successively:

H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ … ⊃ H_{i_{n−k}} ∩ … ∩ H_{i_{n−k−l+1}} = Γ_{1}  (4)

Finally, the polynomial f^{(l)} ∈ IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l}] is assigned to the vertex v. Recall (see section 1) that f^{(l)} is defined on (n − l)-plane Γ_{1}. Besides, v is either labeled or not labeled.

Thus, to different vertices at the level l are attached the different beginnings of flags.

At the inductive step we construct the sons of v. Namely, for any k-face Γ with the same beginning (4) of its representing flag consider the next element of its flag, let it be Γ_{1} ∩H_{i_{n−k−l}}. Construct a son of v to which we attach Γ_{1} ∩ H_{i_{n−k−l}} and assign the polynomial f^{(l+1)} ∈ IR[Z_{1}, …, Z_{k}, Y_{1}, …, Y_{n−k−l−1}]. We label this vertex if and only if Y_{n−k−l}|f^{(l)} (recall that due to the maintainance property, see section 1, the latter condition means that the linear form or the variable Y_{n−k−l} gives a contribution into V ar^{(Γ)}(f)).

This completes the inductive construction of T . The leaves (or paths) of T correspond bijectively to k-faces of S to which the fixed path of T′ corresponds. To each leaf (or path) of T which corresponds to k-face Γ the flag representing Γ H_{i_{n−k}} ⊃ H_{i_{n−k}} ∩ H_{i_{n−k−1}} ⊃ … ⊃ H_{i_{n−k}} ∩ … ∩ H_{i_{1}} = Γ is attached along the path (which is partially labeled).

Now we proceed to estimating the number of leaves of T . For a vertex v consider all its labeled sons (we utilize the introduced above notations). Each labeled son corresponds to a hyperplane H_{i} such that the linear function L_{Γ_{1}∩H_{i}}|f^{(l)}, where L_{Γ_{1}∩H_{i}} is a certain linear function on (n − l)-plane Γ_{1} with the zero set Γ_{1} ∩ H_{i}, being a hyperplane in Γ_{1}, and to different sons correspond different hyperplanes Γ_{1} ∩ H_{i}. Consider the family H of all such hyperplanes H_{i}. First assume that it contains at least m^{c_{3}} hyperplanes. Then the condition 2. of the theorem implies that the number of the connected components b = B_{0}^{(Γ_{1})}({H_{i} ∩ Γ_{1}}_{H_{i}∈H}) of the complement in Γ_{1} of the arrangement ⋃_{H_{i}∈H}(H_{i} ∩ Γ_{1}) is greater than Ω(m^{c_{4}n}). On the other hand the proposition (see section 1) entails that b ≤ 2^{O(s+n−l)} ≤ 2^{O(s+n)}, taking into account that the complexity C(f) = C(f_{1} ⋯ f_{s}) ≤ 2s − 1. This provides the lower bound on the depth of T′, namely, t ≥ s ≥ Ω(n log m), that proves lemma 2. Thus, we can assume that any vertex v of T has less than m^{c_{3}} labeled sons. Besides the labeled sons, each vertex could have at most m unlabeled sons. Furthermore, due to the maintenance property, along each path of T at least c(1 − c_{1})n vertices are labeled (see the inductive step above).

To estimate the number of leaves in T introduce an auxiliary magnitude M(R, Q) to be the maximal possible number of the 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 and with at most Q unlabeled vertices along the path. One can assume w.l.o.g. that Q ≤ R ≤ m (if Q > R then set M(R, Q) = 0, the inequality R ≤ m holds since we consider the subtrees of T , and to each path of T a flag of the length at most m is attached).

Considering such a tree and its subtrees with the roots being the sons (both unlabeled and labeled) of the root of the tree, we get the following inductive inequality:

M(R, Q) ≤ m · M(R − 1, Q − 1) + m^{c_{3}}M(R − 1, Q)

For the base of induction, obviously M(0, 0) = 1. By induction on R we obtain the bound M(R, Q) ≤ β · m^{Q} · m^{(c_{3}+δ_{1})R} for arbitrary δ_{1} > 0 and a suitable β > 0.

Substituting R = n − ⌈c_{1}n⌉, Q = (1 − c)(n − ⌈c_{1}n⌉), we conclude that the number of the leaves of T is less than O(m^{(1−c)(1−c_{1})n+(c_{3}+δ)(1−c_{1})n}) for arbitrary δ > 0.

To complete the proof of lemma 2 it remains to notice that the tree of flags T was constructed for a fixed path of CT T′; there are at most 3^{t} paths of T′. On the other hand, every k-face Γ of S, satisfying the inequality V ar^{(Γ)}(T′) ≥ c(1 − c_{1})n, corresponds to one of the leaves of a tree of flags constructed for one of the paths of T′. Hence the number of such k-faces M ≤ O(3^{t} · m^{(1−c+c_{3}+δ)(1−c_{1})n}).

3 Quadratic complexity lower bound for

RCTs solving the restricted integer pro-

gramming

The restricted integer programming is the arrangement

L_{n,j} = ⋃_{a∈{0,...,j−1}^{n}} {aX = 1} ⊂ IR^{n}

of m = j^{n} hyperplanes for some j ≥ 2 (see e.g. [M85b]). For j = 2 L_{n,2} is the knapsack problem.

As an application of the theorem we prove the following corollary.

Corollary: For any RCT solving the restricted integer programming L_{n,j}, its depth is greater than Ω(n^{2} log j).

To check the conditions 1., 2. of the theorem first take \frac{3}{4} < c_{1} < 1. Any k = ⌈c_{1}n⌉-face Γ of L_{n,j} can be given by n−k linear equations g_{1}, …, g_{n−k} of the form aX = 1 from L_{n,j}. If other linear equations g′_{1}, …, g′_{n−k} from the family L_{n,j} give the same k-face Γ then their linear hulls coincide: L(g_{1}, …, g_{n−k}) = L(g′_{1}, …, g′_{n−k}).

Take a prime j ≤ p < 2j. Let us show that the linear hull L(g_{1}, …, g_{n−k}) contains at most p^{n−k} linear equations from the family L_{n,j}. Consider the linear equations from (L(g_{1}, …, g_{n−k}) ∩ L_{n,j}) mod p (we treat the linear equations as their vectors of the coefficients). Then the results are pairwise distinct vectors, they constitute a family F ⊂ IF_{p}^{n+1}, choose among the elements from F a basis over IF_{p}, it contains at most n − k elements (otherwise, the preimages of F prior taking modp would be linear independent as well). All the vectors from F are the linear combinations over IF_{p} of the elements of the basis, therefore, F contains at most p^{n−k} elements, thus the cardinality |L(g_{1}, …, g_{n−k}) ∩ L_{n,j}| = |F| ≤ p^{n−k}.

Any (n − k)-tuple of the linearly independent linear equations from L_{n,j} provides a k-face. Therefore, any k-face is provided by less or equal to

\binom{p^{n−k}}{n − k} ≤ p^{(n−k)^{2}} ≤ (2j − 1)^{(n−k)^{2}}

number of (n − k)-tuples because of the shown above. On the other hand, denote by I_{l}, 1 ≤ l ≤ n the number of linearly independent l-tuples from L_{n,j}. Obviously, I_{1} = j^{n} − 1. By induction on l for l ≤ n − 1 we have I_{l+1} ≥ \frac{I_{l}(j^{n}−p^{l})}{l+1} again because of the shown above. Hence,

I_{l} ≥ (j^{n} − 1)(j^{n} − p)(j^{n} − p^{2}) ⋯ (j^{n} − p^{l−1})\frac{1}{l!} >
(j^{n} − 1)(j^{n} − 2j)(j^{n} − (2j)^{2}) ⋯ (j^{n} − (2j)^{l−1})\frac{1}{l!} >
j^{nl} (1 − \frac{1 + (2j) + (2j)^{2} + ⋯ + (2j)^{l−1}}{j^{n}} ) \frac{1}{l!} =

j^{nl} (1 − \frac{(2j)^{l} − 1}{(2j − 1)j^{n}} ) \frac{1}{l!}

If l ≤ \frac{n}{2} we have \frac{(2j)^{l}−1}{(2j−1)j^{n}} ≤ \frac{1}{3}, i.e. I_{l} > Ω(\frac{j^{nl}}{l!} ). Substituting l = n − k, we conclude that the number of k-faces ϕ_{k}(L_{n,j}) is greater than

Ω (\frac{j^{(1−c_{1}−δ_{1})n^{2}}}{(2j)^{(1−c_{1})^{2}n^{2}}} ) ≥ Ω (j^{((1−c_{1})(2c_{1}−1)−δ_{1})n^{2}})

for arbitrary δ_{1} > 0. Thus, to satisfy the condition 1. in the theorem one can take c_{2} = (1 − c_{1})(2c_{1} − 1) − δ_{1}.

To justify the condition 2. in the theorem take any k_{1}-face Γ of L_{n,j} where k_{1} ≥ k given by n − k_{1} linear equations g_{1}, …, g_{n−k_{1}} from L_{n,j}, and besides, q ≥ j^{c_{3}n} linear equations h_{1}, …, h_{q} from L_{n,j}. Take a certain 0 < c_{5} < 1 which will be specified later. Denote k_{2} = ⌈c_{5}n⌉. There are \binom{q}{k_{2}} ≥ Ω(j^{c_{5}(c_{3}−δ)n^{2}}) k_{2}-tuples from h_{1}, …, h_{q} for arbitrary δ > 0. If two k_{2}-tuples h_{i_{1}}, …, h_{i_{k_{2}}} and h_{l_{1}}, …, h_{l_{k_{2}}} give the same face in Γ (i.e. a face of L_{n,j}, being a subset of Γ), the linear hulls coincide:

L(g_{1}, …, g_{n−k_{1}}, h_{i_{1}}, …, h_{i_{k_{2}}}) = L(g_{1}, …, g_{n−k_{1}}, h_{l_{1}}, …, h_{l_{k_{2}}})

(cf. above). Therefore, for any face in Γ there are at most \binom{p^{n−k_{1}+k_{2}}}{k_{2}} ≤ (2j)^{c_{5}(n−k_{1}+c_{5}n)n} such k_{2}-tuples (since the latter linear hull contains at most p^{n−k_{1}+k_{2}} linear equations from L_{n,j}, see above). Furthermore, (2j)^{c_{5}(n−k_{1}+c_{5}n)n} ≤ j^{2c_{5}(1−c_{1}+c_{5})n^{2}}. Thus, the number of faces in Γ of the subarrangement S^{(Γ)} = ⋃_{1≤i≤q}(Γ ∩ {h_{i} = 0}) is greater than Ω (j^{c_{5}(c_{3}−δ−2+2c_{1}−2c_{5})n^{2}}).

Now take c_{3} = \frac{1}{2}, then the requirement c_{3}(1−c_{1}) < c_{2} is fulfilled for small enough δ_{1} > 0. Since c_{3} − 2 + 2c_{1} > 0, one could choose c_{5} > 0 and δ > 0 small enough to provide c′_{4} = c_{5}(c_{3} − δ − 2 + 2c_{1} − 2c_{5}) > 0.

Thus, we have proved so far that the number of faces in Γ in the subarrangement S^{(Γ)} is greater than Ω(j^{c′_{4}n^{2}}). Take any 0 < c_{4} < c′_{4}. The required bound 2. of the theorem on the number of the connected components of the complement in Γ of the subarrangement S^{(Γ)} B_{0}^{(Γ)}(Γ∩{h_{1} = 0}, …, Γ∩{h_{q} = 0}) ≥ Ω(j^{c_{4}n^{2}}) (and thereby the corollary) follows from the following general remark (this can be deduced also from [B92], but for the sake of selfcontainess we give a short and elementary proof of it).

Remark: For any arrangement S = ⋃_{1≤i≤m} H_{i} ⊂ IR^{n} and 0 ≤ k ≤ n − 1 the number of k-faces in the arrangement ϕ_{k}(S) < B_{0}(H_{1}, …, H_{m}).

Proof: Intersecting S with a generic (n−k)-plane, we reduce the remark to the case k = 0.

Thus k = 0. Choose a generic hyperplane H and shift it parallel to itself. When it contains a vertex v of S we show that there “appears” a new (in other words, not yet swept) connected component of the complement IR^{n} − S with a vertex v and situated completely on one side of H. Indeed, let v = ⋂_{1≤j≤n} H_{i_{j}} for some H_{i_{1}}, …, H_{i_{n}}. Take the coordinates system with the coordinate hyperplanes H_{i_{1}}, …, H_{i_{n}}. Let H have an equation in these coordinates α_{1}X_{1}+⋯+α_{n}X_{n} = 0, each α_{i} ≠ 0, 1 ≤ i ≤ n, since H is generic. Then the “orthant” {α_{i}X_{i} ≥ 0; 1 ≤ i ≤ n} (which is situated completely on one side of H) contains a connected component of the complement IR^{n} − S with a vertex in v.

So, to each vertex v of S corresponds a connected component of the complement IR^{n} − S. In addition, to the first (in the order of shifting H) vertex v_{1} corresponds also at least one more connected component situated in the “orthant” {α_{i}X_{i} ≤ 0; 1 ≤ i ≤ n} (so on the other side of H) with a vertex in v_{1}, this implies the strict inequality in the remark.

4 Lower bound on the complexity of deter-

ministic computation trees

For CT T′ which recognizes either an arrangement S = S or a polyhedron S = S^{+} given by the hyperplanes H_{1}, …, H_{m}, we can give the similar complexity lower bound Ω(log N) as in the theorem, where N is the number of k-faces of S, without the restriction N ≥ m^{Ω(n)} imposed in the theorem.

Theorem 2: Let CT T′ with the depth t recognize S with N k-faces, and S satisfy the following condition. For any k_{1}-face Γ of S with k_{1} ≥ k and any subset H_{i_{1}}, …, H_{i_{s}} with s ≥ N^{c_{3}/(n−k)} for a certain c_{3} < 1 such that the planes H_{i_{1}} ∩ Γ, …, H_{i_{s}} ∩ Γ are pairwise distinct from Γ, the number of connected componets of the complement in Γ of the arrangement B_{0}^{(Γ)}(H_{i_{1}} ∩ Γ, …, H_{i_{s}} ∩ Γ) ≥ N^{c_{4}} for a suitable c_{4} > 0. Then t ≥ Ω(log N).

The proof follows the proof of the theorem with considerable simplifications. Namely, in lemma 1 one states that V ar^{(Γ)}(T′) = n − k. In lemma 2 we have either the bound 2^{t} ≥ N^{Ω(c_{4})} or the bound N ≤ 3^{t}N^{c_{3}} due to the estimation M(n − k, 0) ≤ N^{c_{3}}.

Notice that the Theorem 2 in case of an arrangement S = S follows from [SY82], [B83] without the condition in the Theorem 2. In case of a polyhedron S = S^{+} a weaker complexity lower bound Ω(log N/ log log N) was proved in Theorem 2 from [GKV96] without the condition of Theorem 2.

5 Open Problem

We were not able to prove any superlinear lower bound or a linear upper bound on the Element Distinctness(cf. [M85a], [GKMS96]) for randomized computational trees. Note that the corresponding lower bound for randomized decision trees is Ω(n log n), [GKMS96].

Acknowledgement

We thank Friedhelm Meyer auf der Heide, Volker Strassen, and Andy Yao for many stimulating discussions.

References

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

[B79] D. Bini, Border Rank of a p × q × 2 Tensor and the Optimal Approximation of a Pair of Bilinear Forms, Proc. ICALP 80, Lecture Notes in Computer Science Vol. 85, Springer-Verlag, 1980, pp. 98– 108.

[BCLR79] D. Bini, M. Capovani, G. Lotti, F. Romassi, O(n^{2.7799}) Complexity for n × n Approximate Matrix Multiplication, Inform. Processing Letters 8 (1979), pp. 234–235.

[B92] A. Björner, Subspace Arrangements, Proc. First European Congress of Mathematicians, Progress in Mathematics, Vol. 119, Birkhäuser, 1992, pp. 321–370.

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

[BPR94] S. Basu, R. Pollack, M.-R. Roy, On the Combinatorial and Algebraic Complexity of Quantifier Elemination, Proc. 35th IEEE FOCS, 1994, pp. 632–641.

[CKKLW95] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, K. Werther, On Real Turing Machines That Toss Coins, Proc. 37th ACM STOC (1995), pp. 335–342.

[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. Comput. Syst. Sci. 16 (1978), pp. 413–417.

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

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

[GK97] D. Grigoriev, M. Karpinski, Randomized Ω(n^{2})Lower Bound for Knapsack, Proc. 29th ACM STOC (1997).

[GKMS96] D. Grigoriev, M. Karpinski, F. Meyer auf der Heide, R. Smolensky, A Lower Bound for Randomized Algebraic Decision Trees, Proc. 28th ACM STOC (1996), pp. 612–619; submitted to Computational Complexity.

[GKS96] D. Grigoriev, M. Karpinski, R. Smolensky, Randomization and the Computational Power of Analytic and Algebraic Decision Trees; submitted to Computational Complexity.

[GKV95] D. Grigoriev, M. Karpinski, N. Vorobjov, Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees, Proc. 36th IEEE FOCS (1995), pp. 258–265; also to appear in Discrete and Computational Geometry, 1996.

[GKV96] D. Grigoriev, M. Karpinski, N. Vorobjov, Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees, Discrete and Computational Geometry, 1996.

[GKY96] D. Grigoriev, M. Karpinski, A. Yao, An Exponential Lower Bound on the Size of Algebraic Decision Trees for the MAX, submitted to J. Computational Complexity.

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

[KV88] M. Karpinski, R. Verbeek, Randomness, Provability, and the Separation of Monte Carlo Time and Space, LNCS, 270 (1988), Springer-Verlag, 1988, pp. 189–207.

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

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

[M64] J. Milnor, On the Betti Numbers of Real Varieties, Proc. AMS, 1996, v. 15, pp. 275–280.

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

[MPR94] L. Montana, L. Pardo, T. Recio, A Note on Rabin’s Width of a Complete Proof, Computational Complexity, 1994, v. 4, p. 12–36.

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

[R72] M. Rabin, Proving Simultaneous Positivity of Linear Forms, J. Comput. Syst. Sci., 1972, v. 6, p. 639–650.

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

[S90] V. Strassen, Algebraic Complexity Theory, in Handbook of Theoretical Computer Science, vol. A, 1990, Elsevier, pp. 633–672.

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

[W68] H. Warren, Lower Bounds for Approximation of Nonlinear Manifolds, Trans. AMS, 1968, v. 133, pp. 167–178.

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

[YI65] S. Yajima, T. Ibarak, A Lower Bound on the Number of Threshold Functions, IEEE EC, 1965, V. 14, pp. 926–929.