BRICS RS-98-11 Frandsen et al.: Lower Bounds for Dynamic Algebraic Problems BRICS

Basic Research in Computer Science

Lower Bounds for Dynamic Algebraic Problems

Gudmund Skovbjerg Frandsen Johan P. Hansen Peter Bro Miltersen BRICS Report Series RS-98-11 ISSN 0909-0878 May 1998 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1998, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/98/11/

Lower bounds for dynamic algebraic problems

Gudmund Skovbjerg Frandsen^{∗}

BRICS^{†}

Department of Computer Science, University of Aarhus, DK-8000 Aarhus C, Denmark.

Johan P. Hansen Department of Mathematics, University of Aarhus, DK-8000 Aarhus C, Denmark.

Peter Bro Miltersen^{∗} BRICS^{†} Department of Computer Science, University of Aarhus, DK-8000 Aarhus C, Denmark.

∗Supported by the ESPRIT Long Term Research Programme of the EU under project number 20244 (ALCOM-IT).

†Basic Research in Computer Science, Centre of the Danish National Research Foundation

Abstract

We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x_{1}, …, x_{n}) = (y_{1}, …, y_{m}) is an algebraic problem, we consider serving on-line requests of the form “change input x_{i} to value v” or “what is the value of output y_{i}?”. We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix-vector product, dynamic matrix multiplication and dynamic discriminant and an Ω(\sqrt{n}) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate’s O(\sqrt{n log n}) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint and matrix inverse and an Ω(\sqrt{n}) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)^{2}/ log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.

1 Introduction

1.1 Setup

Reif and Tate [RT97] considered the following setup of dynamic algebraic algorithms. Let f_{1}, …, f_{m} be a system of n-variate polynomials over a commutative ring or rational functions over a field. We seek an algorithm, that, when given an initial input vector x = (x_{1}, x_{2}, …, x_{n}) to the system, does some preprocessing and then afterwards is able to efficiently handle on-line requests of two forms: “change_{k}(v): Change x_{k} to the new value v” and “query_{k}: Return the value of output f_{k}(x)”. Several natural concrete examples were given by Reif and Tate, including dynamic polynomial evaluation, dynamic matrix-vector multiplication, dynamic matrix-matrix multiplication, dynamic polynomial multiplication, and dynamic discrete Fourier transform. Reif and Tate provided two general techniques for the design of efficient dynamic algebraic algorithms. They also presented lower bounds and time-space trade-offs for several problems. Apart from Reif and Tate’s work, we also meet dynamic algebraic problems in the literature on the prefix sum problem [Fre82, Fre81, Yao85, HF93, FS89, BAG91]; the specific case of f_{i}(x) = ∑_{j=1}^{i} x_{i} for i = 1, …, n.

The aim of this paper is to present three techniques for showing lower bounds for dynamic algebraic problems. We use them to show lower bounds on the worst case time complexity per operation for several natural problems where Reif and Tate had no lower bounds or only lower bounds for the timespace trade-off.

1.2 Problems considered

Given a commutative ring R, we look at the following systems of functions.

matrix-vector multiplication : R^{n^{2}+n} ↦ R^{n}. The first n^{2} components of the input are interpreted as an n×n matrix A, the last n components are interpreted as an n-vector x, and Ax is returned.

matrix multiplication : R^{2n^{2}} ↦ R^{n^{2}}. The input is interpreted as two n × n matrices which are multiplied.

convolution : R^{2n} ↦ R^{2n}: The input is interpreted as two n-vectors x = (x_{0}, …, x_{n−1}) and y = (y_{0}, …, y_{n−1}), whose convolution is returned. That is, the i’th component of the output is z_{i} = ∑_{j+k=i} x_{j}y_{k}.

determinant : R^{n^{2}} ↦ R: The input is interpreted as a matrix, whose determinant is returned.

matrix adjoint : R^{n^{2}} ↦ R^{n^{2}} is the function that maps an n×n matrix A into the corresponding adjoint matrix given by matrix adjoint(A)_{ij} = (−1)^{i+j} det(A_{ji}), where A_{ji} denotes the (n − 1) × (n − 1) matrix resulting when deleting the j’th row and the i’th column from A.

If k is a field, matrix inverse : k^{n^{2}} ↦ k^{n^{2}} is the partial function that maps a nonsingular n × n matrix A into the corresponding inverse matrix A^{−1}. Note that for a nonsingular matrix, matrix inverse(A) = \frac{1}{det A}matrix adjoint(A).

discriminant : R^{n} ↦ R: The discriminant of the polynomial for which the n inputs are roots is returned, i.e.

discriminant(x_{1}, …, x_{n}) = ∏_{i≠j}(x_{i} − x_{j})

symmetric : R^{n} ↦ R^{n}. All n elementary symmetric polynomials of the inputs are computed, i.e., the j’th component of the output is

y_{j} = ∑_{I⊆{1,2,...,n},|I|=j} ∏_{i∈I} x_{i}

polynomial evaluation : R^{n+2} ↦ R. A vector (x, a_{0}, a_{1}, …, a_{n}) is mapped to a_{0} + a_{1}x + a_{2}x^{2} + … + a_{n}x^{n}.

Finally, the following problem is defined for any algebraically closed field k. Let ω be a primitive n’th root of unity k, and let F be the n × n matrix F = (ω^{ij})_{i,j}. The Discrete Fourier Transform dft : k^{n} ↦ k^{n}, is the map x → F x.

1.3 Models of computation

A pivotal issue when considering lower bounds is the model of computation. For dynamic algebraic problems, this issue is quite subtle; models can vary according to the algebraic domain (reals, integers, finite fields, etc.), the atomic operations allowed (only arithmetic operations or more general operations), and the possibility of influencing the control flow of the solution (to what extent is the sequence of atomic operations performed allowed to depend on the previous history of the algorithm). We prove lower bounds in the following models of computation.

The straight line program model. This is the most basic model. Given the problem of dynamic evaluation of a function f : k^{n} ↦ k^{m}, we assign a straight line program to each of the operations change_{1}, change_{2}, …, change_{n}, query_{1}, query_{2}, …, query_{m}. The programs corresponding to the change-operations take a single input x and have no output, while the programs corresponding to the query-operations have no input but one output. Each program is a sequence of instructions of the form y_{i} ← y_{j} ∘ y_{k}, where ∘ ∈ {+, −, ∗, /}, and y_{j} and y_{k} are either input variables, memory variables, or constants. We could also assign a program to the initialization operation. However, we find it more convenient to assume that we always initialize to some specific vector (say, (0, 0, 0, …, 0)). Then, we just need to assign an initial value to each variable which appears somewhere in one of the programs. Then, the complexity of a solution is the length of the longest program in the solution.

History dependent algebraic computation trees. In the straight line program model, it is not possible for the algorithm to modify the sequence of atomic operations performed. In the history dependent algebraic computation tree model, we allow the algorithm to control the sequence in a strong way. First, instead of assigning straight line programs to operations, we assign algebraic computation trees. As branching nodes, we do not just allow <-comparison (which only makes sense for certain fields), instead we allow branching according to arbitrary predicates of finite arity. Also, to each operation (such as change_{12}) we assign not one, but several (in fact infinitely many) algebraic computation trees: One for each history, where a history is every bit of discrete information the system has obtained so far; namely, the sequence of input variables that were changed and output variables that were queried, and the result of every branching test made so far during the execution of the operations performed. When we execute an operation, we find the tree corresponding to the current history and execute that. The complexity of a solution is the depth of its deepest tree.

Random access machine models. A very general way of defining RAM models is outlined by Ben-Amram and Galil [BAG92]. Here, we will only give an informal discussion. A RAM has an infinite number of registers, indexed by the integers. It also has a finite number of CPU-registers with proper names. Each register contains an element of the domain of computation: if we consider computation over the reals, each register contains a real; if we consider computation over the integers, each register contains an integer. In any case, it is convenient if the integers (or at least a sufficiently large subset of the integers) is a subset of the domain of interest; this makes indirect addressing possible, an important feature of the RAM. The machine operates on the memory using a finite program containing the following kinds of instructions: direct and indirect reads and writes, conditional jumps and a finite number of atomic computational instructions operating on the CPU-registers. Each instruction is executed at unit cost. When the domain of the registers is the set of integers and the atomic operations are +, −, ∗, we get the integer RAM. Another model of interest is the generalized real RAM [BAG92]. Here, the registers contain arbitrary reals and as atomic operations we allow any set of functions ℝ^{c} ↦ ℝ for a constant c, with the property that for some countable closed set C ⊂ ℝ^{c}, each function is continuous in ℝ^{c} \ C.

The word RAM [FW93, FW94, Hag98] has a somewhat different flavor from the integer RAM and the real RAM. The integer RAM can be considered unreasonably powerful, since it can handle arbitrary integers with unit cost. Then again, the user can give it any sequence of n integers as input and measure the complexity of the computation as a function of n. The word RAM is the result of relaxing the power of both parties, the algorithm and the user. The word RAM does computation on words, i.e. integers in {0, 1, …, 2^{w} − 1} for some parameter w, intuitively determined at compiletime. The RAM has registers indexed by {0, 1, …, 2^{w} −1}; in particular, we assume w ≥ log n, so that the input can be given in registers and read. The RAM can operate on words using a number of unit cost operations including addition, subtraction, multiplication, integer division, bitwise Boolean operations, and left and right shifts. The algorithm should be correct for any value of w ≥ log n, but n, the number of words in the problem, should be the only variable appearing in the time bound. The word RAM has been extensively studied as a model for sorting and searching. For instance, Andersson et al [AHNR95] show that sorting n words can be done in time O(n log log n) on a word RAM. The survey of Hagerup [Hag98] gives a good overview of these results. When considered as a model for dynamic algebraic problems, the word RAM is appropriate when the function in question is a constant degree polynomial over the integers. This ensures that when the input is a sequence of single words, i.e. integers in {0, 1, …, 2^{w} − 1}, the output can be given in a constant number of words, i.e. we can at least write the output with unit cost. For instance, dynamic matrix multiplication makes good sense in the word RAM model while we will not consider dynamic determinant in this model.

1.4 Our results

We present three techniques for proving lower bounds for dynamic algebraic problems. The first technique is very robust. In particular, it holds under a wide range on assumptions about the algebraic domain and the operations allowed, and even if the algorithm is allowed to control the flow of computation in strong ways. The technique is closely related to the incompressibility technique of Ben-Amram and Galil [BAG92]. The second technique holds only for the word RAM model (where the first technique fails). It is a modest extension of communication complexity techniques of Miltersen et al [MNSW95]. With the first and second technique we show

Theorem 1 Any solution to dynamic matrix-vector multiplication, matrix multiplication, matrix adjoint, matrix inverse, determinant, polynomial evaluation or discriminant has worst case complexity Ω(n) per operation and any solution to dynamic convolution or symmetric has worst case complexity Ω(\sqrt{n}) per operation, in the following models of computation:

• Straight line programs over any fixed finite field (except for polynomial evaluation, discriminant and symmetric), with the allowed set of change-arguments being the field itself.

• History dependent algebraic computation trees over any infinite field, with the allowed set of change-arguments being any infinite subset of the field.

• The integer RAM (except for matrix inverse), with the allowed set of change-arguments being any infinite subset of the integers, and the generalized real RAM, with the allowed set of change-arguments being the reals.

• The word RAM (except for matrix adjoint, matrix inverse, determinant, discriminant, polynomial evaluation and symmetric), with the allowed set of change-arguments being the set of words.

We should note that the lower bound for dynamic polynomial evaluation was also proved by Reif and Tate, though not for as wide a range of models as above. Reif and Tate present lower bounds for a number of other problems by reductions from polynomial evaluation; we can apply the same reductions to get the lower bounds in the wider range of models.

We should also note that for certain models and certain of the above problems, there is an easier way of showing the same lower bound. For instance, we can show a lower bound for dynamic matrix-vector multiplication over the reals using arithmetic operations as follows: It is well known [Win67, Win70] that n × n matrices A over the reals exist so that computing x → Ax requires Ω(n^{2}) arithmetic operations. Now, given an alleged dynamic algorithm for dynamic matrix-vector multiplication with complexity o(n) per operation, we can initialize the matrix input to this matrix. Then, we can evaluate Ax for any given x using n change and n query operations, i.e., a total of o(n^{2}) arithmetic operations, a contradiction. The same technique was, in fact, used by Reif and Tate to show the lower bounds of their paper (using the fact that explicit hard polynomials exist, rather than the fact that explicit hard matrices exist). However, this argument does not seem to generalize to show, for instance, the linear lower bound for straight line programs over a finite field (where matrices requiring Ω(n^{2}) arithmetic operations do not exist [Sav74]), nor to show any lower bound for the generalized real RAM or the word RAM. Also, our technique applies to a wider variety of problems in a uniform way.

Our third technique is more fragile. It only works in the model of history independent straight line programs. A technical ingredient of the technique is the lower bound for depth-two superconcentrators by Radhakrishnan and Ta-Shma [RTS97]. With the third technique we show

Theorem 2 Any solution to dynamic dft in the straight line program model over an algebraically closed field of characteristic 0, with change-arguments restricted to any infinite subset of the field, has worst case complexity Ω((log n)^{2}/ log log n) per operation.

1.5 Optimality (and otherwise) of results

The lower bounds for matrix-vector multiplication and matrix multiplication are tight, there are straightforward linear upper bounds. The lower bound for discriminant is also tight, there is a linear upper bound for any infinite field (see Theorem 3), and a straightforward constant upper bound for any finite domain in the straight line program model. Interestingly, the linear upper bound does not seem to be implementable in the straight line program model. The lower bound for convolution has a fairly good match in the O(\sqrt{n log n}) upper bound of Reif and Tate [RT97] for the same problem. The upper and lower bounds for determinant, matrix adjoint, matrix inverse and symmetric are not tight, we don’t know any solution for determinant, matrix adjoint and matrix inverse better than evaluating queries from scratch, and we don’t know any better upper bound for dynamic symmetric than a (not quite obvious) change_{i}(v) : assume x_{i} = v_{k} for [v_{k}, n_{k}] ∈ L; if n_{k} > 1 then n_{k} := n_{k} − 1

else D := D/ ∏_{j≠k}(−1)(v_{j} − v_{k})^{2}; L := L \ {[v_{k}, 1]};

if v = v_{l} for some [v_{l}, n_{l}] ∈ L then n_{l} := n_{l} + 1
else D := D · ∏_{j}(−1)(v_{j} − v)^{2}; L := L ∪ {[v, 1]};
x_{i} := v;

Figure 1: Computation tree solution for discriminant.

O(n) upper bound (see Theorem 4).

Reif and Tate show an O(\sqrt{n}) upper bound for dynamic dft which is valid in the straight line program model. This leaves a rather large gap between upper and lower bounds. Our third technique is inherently unable to show better lower bounds than a constant times (log n)^{2}/ log log n, this quantity being the average number of edges per input/output-vertex in an optimal depth 2 superconcentrator.

Theorem 3 There is a computation tree solution of complexity O(n) for dynamic evaluation of discriminant. The solution works over any field.

Proof. All the current inputs x_{1}, …, x_{n} are maintained, and so is the set of their (distinct) values together with the number of occurrences in L = {[v_{1}, n_{1}], …, [v_{|L|}, n_{|L|}]}, i.e. n_{i} ≥ 1 and ∑_{i} n_{i} = n. Finally, we maintain the (nonzero) discriminant of the distinct values: D = ∏_{i≠j}(v_{i} − v_{j}).

With this representation query is simple; if all n_{i}’s are 1, we return D, otherwise we return 0. For change, we must update D and L, which is easily done in linear time (see Figure 1).

Theorem 4 There is a straight line program solution of complexity O(n) for symmetric. The solution works over any commutative ring.

Proof. All the current inputs x_{1}, …, x_{n} and corresponding outputs y_{1}, …, y_{n} are maintained. This makes the straight-line program for query_{i} trivial; it needs only return y_{i}. For the implementation of change, we observe that for any i, k, we have that y_{k} = x_{i}z_{k−1,i} + z_{ki}, where z_{ki} does not depend on x_{i}, which makes the solution in Figure 2 valid.

change_{i}(v) : z_{0} := 1;

for k = 1 … n do

z_{k} := y_{k} − x_{i}z_{k−1};

y_{k} := z_{k} + vz_{k−1};

x_{i} := v;

Figure 2: Straight line solution for symmetric.

1.6 Organization of paper

In Section 2, we present our first technique as it applies to the case of history dependent algebraic computation trees and then show how to generalize it to straight line programs over a finite field, the integer RAM, and the generalized real RAM. The lower bounds for the word RAM are presented in Section 3. In Section 4, we present the technique based on superconcentrators and its application to dft.

2 Incompressibility based lower bounds

Our technique is essentially based on the following incompressibility statement: If k is an algebraically closed field, a rational map k^{n} ↦ k^{n−1} can not be injective. Thus, it is closely related to the technique of Ben-Amram and Galil, who applied incompressibility in various domains to show a gap between the power of random access machines and pointer machines [BAG92].

First, a technical lemma stating a generalization of the above fact. Let k be an algebraically closed field. Recall that an algebraic subset W ⊂ k^{n} is an intersection of sets of the form {x ∈ k^{n}|p(x) = 0}, where p is a non-trivial multivariate polynomial.

Lemma 5 Let k be an algebraically closed field. Let W be an algebraic subset of k^{m} and let ϕ = (f_{1}/g_{1}, …, f_{n}/g_{n}) : k^{m} \ W ↦ k^{n} be a rational map where f_{i}, g_{i} ∈ k[x_{1}, …, x_{m}] for i = 1, …, n. Assume that there exists y ∈ k^{n} such that ϕ^{−1}(y) is non-empty and finite. Then m ≤ n.

Proof.

1. reduction. We can assume that y = (0, …, 0).

Otherwise let y = (y_{1}, …, y_{n}) and replace (\frac{f_{1}}{g_{1}} , …, \frac{f_{n}}{g_{n}} ) with

(\frac{f_{1}}{g_{1}} − y_{1}, …, \frac{f_{n}}{g_{n}} − y_{n}).

2. reduction. We can assume that W is the set of common zeroes of g_{1}, …, g_{n}.

Otherwise let x ∈ ϕ^{−1}(y) \ W and choose a polynomial g that vanishes on W with g(x) ≠ 0. Consider the rational function

ϕ̃ = (\frac{f_{1}g}{g_{1}g} , …, \frac{f_{n}g}{g_{n}g} ) : k^{m} \ Z(g) ↦ k^{n}

where Z(g) is the zeroes of g. As x ∈ ϕ̃^{−1}(y) ⊆ ϕ^{−1}(y) it is enough to prove the claim for ϕ̃.

3. reduction. We can assume that W is the empty set, and ϕ is a polynomial function.

Otherwise, we assume that y = (0, …, 0), and that W is the set of common zeroes of g_{1}, …, g_{n}. Consider the polynomial function

ϕ̃ = (f_{1}, …, f_{n}, x_{m+1} · g_{1} · . . . · g_{n} − 1) : k^{m+1} ↦ k^{n+1}

The fiber ϕ̃^{−1}(0, …, 0) consists of the tuples (x_{1}, …, x_{m}, x_{m+1}) such that ϕ(x_{1}, …, x_{m}) = (0, …, 0) and such that x_{m+1} = \frac{1}{g_{1}(x_{1},...,x_{m})·...·g_{n}(x_{1},...,x_{m})} which by assumptions on ϕ is non-empty and finite. Therefore it is enough to prove the claim for polynomial functions with y = (0, …, 0) which follows from Lemma 6 below.

Lemma 6 Let k be an algebraically closed field. Assume that the set of common zeroes of f_{i} ∈ k[x_{1}, …, x_{m}] for i = 1, …, n is non-empty and finite. Then m ≤ n.

Proof. Let X be the set of common zeroes and consider A(X), the coordinate ring of polynomial functions on X. By finiteness of X we conclude that

A(X) = ∏_{P ∈X} A(P) = ∏_{P ∈X} k

is a finite dimensional vector space over k. The ideal ℳṔ = ∏_{P ∈X∧P ≠Ṕ} A(P) is a maximal ideal for all Ṕ ∈ X.

Let 𝒫 be a prime ideal in A(X), then 𝒫 = ℳṔ for some Ṕ ∈ X. Otherwise we obtain a contradiction by choosing for each P ∈ X a h_{P} ∈ ℳ_{P} \ 𝒫 and considering 0 = ∏_{P ∈X} h_{P} ∉ 𝒫.

As k is algebraically closed, Hilbert’s Nullstellensatz (cf. [Eis95], Theorem 1.6) gives that

A(X) = k[x_{1}, …, x_{m}]/Rad(f_{1}, …, f_{n})

where Rad(f_{1}, …, f_{n}) is the radical ideal of (f_{1}, …, f_{n}).

A minimal prime ideal of (f_{1}, …, f_{n}) in k[x_{1}, …, x_{m}] is also a minimal prime ideal of Rad(f_{1}, …, f_{n}) and from above a maximal ideal in k[x_{1}, …, x_{m}]. According to Krull’s Principal Ideal Theorem (cf. [Eis95], Theorem 10.2) we have that m = dim k[x_{1}, …, x_{m}] ≤ n

We shall also need the following version of the well-known “Schwartz-Zippel Lemma”.

Lemma 7 Let k be a field.

(i) Let T ⊂ k be finite. If a multivariate polynomial q ∈ k[x_{1}, …, x_{n}] of total degree deg q ≤ |T | is not the zero-polynomial, then q(a) = 0 for at most a fraction \frac{deg q}{|T |} of all the n-tuples a ∈ T^{n}.

(ii) Let S ⊂ k be infinite (implying that k is infinite), and let W be a proper algebraic subset of k^{n}. Let p be a multivariate polynomial in n variables. If p is identically zero as a function restricted to S^{n} \ W, then p is the zero-polynomial.

Proof. The statement of part (i) is adapted from a paper by Schwartz [Sch80]. For part (ii) assume that there is a multivariate polynomial q (that is not the zero-polynomial) such that W ⊆ {x ∈ k^{n}|q(x) = 0}. It follows (by part (i)) that if p is not the zero polynomial and if |T | > deg p + deg q, then there exists a ∈ T^{n} \ W such that p(a) ≠ 0.

Definition 8 Let k be a field.

(i) Let B be an arbitrary set. A function f : k^{n} ↦ B is quasi-injective if there is a proper algebraic subset W ⊂ k^{n} such that f^{−1}(f(a)) is finite for all a ∈ k^{n} \ W.

(ii) Let f : k^{n} ↦ k^{m} be a function. Let X = {x_{1}, …, x_{n}} be the set of inputs. Let X_{1} ⊂ X of size l. Permute the variables of f so that the variables of X_{1} are first, and view f as a function f : (k^{l} × k^{n−l}) ↦ k^{m}. f is said to specialize quasi-injectively (injectively) to X_{1} if the function F : k^{n−l} ↦ (k^{l} ↦ k^{m}) is quasi-injective (injective), where F maps a ∈ k^{n−l} into f_{a}, the function arising from specializing f to the constant vector a on the input set X \ X_{1}.

Remark. F being quasi-injective means that for almost all a there are only finitely many b such that f_{a} and f_{b} are identical functions. An example of a function specializing injectively is matrix-vector multiplication: Different matrices over a field represent different linear maps. Thus, matrix-vector multiplication specializes injectively to the n variables representing the vector-part of the input.

Theorem 9 Let k be an algebraically closed field. Let the polynomial function f : k^{n} ↦ k^{m} specialize quasi-injectively to some set X_{1} of size l. Then any history dependent algebraic computation tree solution for dynamic evaluation of f has complexity at least \frac{n−l}{2(l+m)}.

Proof. (After permutation of indices) we may assume X_{1} = {x_{1}, …, x_{l}}. Let a family of algebraic computation trees solving dynamic evaluation of f be given, and let the max depth of any computation tree representing a

change or query be d.

Consider the specific off-line solution P = P_{1}; P_{2} for f that arises from using change/query-operations in the following order:

P_{1} : change_{l+1}(z_{1}); ⋯; change_{n}(z_{n−l})
P_{2} : change_{1}(x_{1}); ⋯; change_{l}(x_{l}); y_{1} := query_{1}; ⋯; y_{m} := query_{m}

¿From the algebraic computation tree P = P_{1}; P_{2}, we are going to construct a straight line program Q = Q_{1}; Q_{2} that computes f when inputs, i.e. arguments (x_{1}, …, x_{l}, z_{1}, …, z_{n−l}) to change-operations, are restricted to be tuples in k^{n} \ W, where W is a proper algebraic subset of k^{n}. Let L be the number of leaves in the computation tree P. Let D = 2^{d(n+m)}, i.e. D is an upper bound on the degree of any polynomial/rational function occurring in any intermediate result in P. Let T ⊂ k be a finite subset of k satisfying that |T | > L(D + deg f). Divide the elements of T^{n} in L classes C_{1}, …, C_{L} such that any n-tuple a ∈ C_{i} when given as argument to change-operations will make the computation of P follow the path to leaf number i. Clearly, some C_{i} must have size at least |T |^{n}/L, and without loss of generality assume that |C_{1}| ≥ |T |^{n}/L. Let Q = Q_{1}; Q_{2} be the straight-line program arising from the computation path induced by C_{1} with all branching tests removed. Then Q computes f̃: C_{1} ↦ k^{m}, for some rational function f̃ = (\frac{p_{1}}{q_{1}} , …, \frac{p_{m}}{q_{m}}) that is defined on all of C_{1} and since none of the q_{i}’s are the zero-polynomial, Q can be extended to be defined on all of k^{n} except for a proper algebraic subset W defined by q_{1}, …, q_{m}. Since f̃ is identical to the polynomial function f for the restricted input set C_{1}, it follows by Lemma 7(i) that Q does compute the polynomial function f whenever no division by zero occurs, i.e. for inputs restricted to k^{n} \ W.

We observe that there exists a proper algebraic subset W_{1} ⊂ k^{n−l} such that for all a ∈ k^{n−l}\W_{1}, we can find a proper algebraic subset W_{a} ⊂ k^{l} such that the straight-line program Q = Q_{1}; Q_{2} will compute f(x, a) correctly for all a ∈ k^{n−l} \ W_{1}, and x ∈ k^{l} \ W_{a}.

For given (n − l)-tuple a ∈ k^{n−l} \ W_{1}, we may specialize the inputs of Q_{1} to a, resulting in program Q_{a} such that Q_{a}; Q_{2} computes the polynomial function f_{a} restricted to k^{l} \ W_{a}.

Let V_{1} ⊆ V denote the set of variables read by the program Q_{2}. By assumption |V_{1}| ≤ 2(l + m)d.

Let Ṽ_{1} denote the values of the variables V_{1} after the execution of Q_{a} but before the execution of Q_{2}, and let f̃denote the unique (by Lemma 7(ii)) polynomial function that extends the rational function (from X_{1} = {x_{1}, …, x_{l}} to Y = {y_{1}, …, y_{m}}) computed by program Q_{2}.

Clearly, Ṽ_{1} is a rational function of a. Let g : (k^{n−l} \ W_{1}) ↦ k^{|V_{1}|} denote this function. Similarly, f̃ is a function of Ṽ_{1}, since Q_{2} does only depend on a through the intermediate values Ṽ_{1}. Let h : codomain(g) ↦ (k^{l} ↦ k^{m}) denote this function. We see that F = h ∘ g. Since F by assumption is quasi-injective, so must also g be quasi-injective and by Lemma 5 this is only possible for |V_{1}| ≥ n − l.

Combining the two inequalities for |V_{1}|, we get n − l ≤ |V_{1}| ≤ 2(l + m)d, i.e. d ≥ \frac{n−l}{2(l+m)}.

Theorem 9 can be used to show lower bounds for a setting where the computation is over an algebraically closed field and arguments to changeoperations are arbitrary elements thereof. We now give a generalization of Theorem 9 needed to get the lower bounds claimed in Theorem 1, i.e., when the computation is over an arbitrary field and the arguments allowed to change-operations an infinite subset thereof. We also need this generalization to get the lower bound for the integer RAM. Note that we can without loss of generality assume that the field is algebraically closed, since, if it is not, we can just consider computation in its algebraic closure.

Theorem 10 Let k be an algebraically closed field. Let the polynomial function f : k^{n} ↦ k^{m} specialize quasi-injectively to some set X_{1} of size l.

Then, for any infinite subset S ⊆ k it holds that any proposed history dependent algebraic computation tree solution for dynamic evaluation of f that is correct when arguments to change-operations are restricted to be elements of S must have complexity at least \frac{n−l}{2(l+m)}.

Proof. This is essentially a repetition of the proof of Theorem 9. In the terminology of that proof, one must observe that when constructing the straight-line program Q, we only need to know that the original dynamic solution works properly when arguments to change-operations are restricted to some sufficiently large finite subset T ⊂ k. By choosing T ⊂ S the entire proof of Theorem 9 carries over.

2.1 Applications

In this section we show, using Theorem 10, the lower bounds that were claimed for the history dependent algebraic computation tree model in Theorem 1 of the Introduction.

Different matrices over a field represent different linear maps. This means matrix-vector multiplication specializes injectively to the n variables representing the vector-part of the input and Theorem 10 gives us that any solution to dynamic matrix-vector multiplication in the history dependent algebraic computation tree model over a field with arguments of change-operations restricted to some infinite subset of the field has complexity Ω(n). Similarly, polynomial evaluation over an infinite field specializes injectively to its first input, yielding an Ω(n) lower bound for dynamic polynomial evaluation. Since matrix-vector multiplication is a specialization of matrix-matrix multiplication, an Ω(n) lower bound holds for dynamic matrix multiplication.

We may construct a dynamic solution for matrix multiplication from a dynamic solution for matrix adjoint or matrix inverse using the following fact:

matrix adjoint ( \begin{matrix}I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{matrix} ) = ( \begin{matrix}I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{matrix} )^{−1} = ( \begin{matrix}I & −A & AB \\ 0 & I & −B \\ 0 & 0 & I \end{matrix} ) ,

where A, B are square matrices of dimension \frac{n}{3} and I is the identity matrix of that dimension. Thus, the Ω(n) lower bound also holds for matrix adjoint and matrix inverse.

We may construct a dynamic solution for matrix adjoint from a dynamic solution for determinant (of the same matrix), when noting that changing the (ij)’th entry in a matrix A by Δ, changes the determinant

matrix adjoint.change_{ij}(v) : x_{ij} := v;

determinant.change_{ij}(v);

matrix adjoint.query_{ij} :  z := determinant.query;

determinant.change_{ji}(x_{ji} + 1); w := determinant.query; determinant.change_{ji}(x_{ji}); return (w − z);

Figure 3: matrix adjoint reduces to determinant.

by Δ · (−1)^{i+j} det A_{ij}, where A_{ij} is the submatrix arising from deleting the ith row and jth column (Figure 3). Thus, we also have an Ω(n) lower bound for determinant.

Next, we show the lower bound for convolution. We can specialize convolution to a function g : k^{n+\sqrt{n}} ↦ k^{\sqrt{n}} by setting y\sqrt{n} = y_{\sqrt{n}+1} = ⋯ = y_{n} = 0 and ignoring all outputs but z_{\sqrt{n}−1}, z_{2\sqrt{n}−1}, …, z_{n−1}. Now g is computing a matrix vector product:

g(( \begin{matrix}x_{\sqrt{n}−1} & x_{\sqrt{n}−2} & ⋯ & x_{0} \\ x_{2\sqrt{n}−1} & x_{2\sqrt{n}−2} & ⋯ & x\sqrt{n} \\ ⋮ & & ... & ⋮ \\ x_{n−1} & x_{n−2} & ⋯ & x_{n−\sqrt{n}} \end{matrix} ) , ( y_{0} ; y_{1} ; ⋮ ; y_{\sqrt{n}−1} )) = ( z_{\sqrt{n}−1} ; z_{2\sqrt{n}−1} ; ⋮ ; z_{n−1} )

Hence, we get the Ω(\sqrt{n}) lower bound for convolution from the Ω(n) lower bound for matrix-vector multiplication.

For the discriminant function, we need to apply Theorem 10 again. discriminant specializes quasi-injectively to its first input: Let discriminant_{a} : k ↦ k denote the function arising from substituting a ∈ k^{n−1} for the remaining inputs, i.e. discriminant_{a}(x) = D(a)(−1)^{n−1} ∏_{i=2}^{n}(x−a_{i})^{2}, where D denotes the discriminant function on only n − 1 roots. Observe that if discriminant_{a} and discriminant_{b} are identical functions and D(a) ≠ 0, then the coordinates of a and b must be identical up to a permutation, and since there is only (n − 1)! distinct permutations on n − 1 elements, then the function F : k^{n−1} ↦ (k ↦ k) is quasi-injective, where F (a) = discriminant_{a}, and by Theorem 10 we have proved an Ω(n) lower bound for discriminant.

For the symmetric function, we also need to apply Theorem 10 again. Assume, for convenience, that n is a perfect square. Let X_{1}, Y_{1} be the following subsets of inputs and outputs respectively: X_{1} = \{x_{1}, …, x\sqrt{n}\}, Y_{1} = \{y\sqrt{n}, y_{2\sqrt{n}}, …, y_{n}\}, and let π_{Y_{1}} : k^{n} ↦ k^{\sqrt{n}} be the projection that ignores all outputs but those in Y_{1}. In fact, π_{Y_{1}} ∘ symmetric specializes quasi-injectively to the inputs in X_{1}. To see this, observe that if a ∈ k^{n−\sqrt{n}}, x ∈ k^{\sqrt{n}}, y = symmetric_{a}(x) and σ_{l} is the lth elementary symmetric function (of all arities and σ_{0}(·) = 1), then y_{k\sqrt{n}} = ∑_{i=0}^{√\overline{n}} σ_{i}(x) · σ_{k\sqrt{n}−i}(a). Since σ_{i}(x) is a form of degree i, it follows (by Lemma 7) that y_{k\sqrt{n}} as a function of x ∈ k^{\sqrt{n}} uniquely determines σ_{k\sqrt{n}−i}(a) for i = 0, …, \sqrt{n}. Consequently, for a, b ∈ k^{n−\sqrt{n}}, we have that π_{Y_{1}} ∘ symmetric_{a} = π_{Y_{1}} ∘ symmetric_{b} if and only if a and b are identical up to a permutation of entries. By Theorem 10, we have an Ω(\sqrt{n}) lower bound for symmetric.

2.2 Lower bounds for straight line programs over finite fields

In this section, we show our lower bounds for straight line programs over finite fields. We also show certain weak lower bounds when branching is allowed. Note that in a finite domain, we cannot hope for lower bounds in the history dependent algebraic computation tree model, since we may encode the entire input vector as part of the history, yielding a constant upper bound for every problem. The natural model to consider is history independent computation trees, with the allowed branching instructions being arbitrary predicates on two variables. In this model, Fredman [Fre82] showed a lower bound of Ω(log n/ log log n) for the prefix sum-problem over 𝔽_{2}. By reduction, one gets the same lower bound for matrix-vector multiplication and the related problems. We get a slightly better Ω(log n) lower bound for the latter problems by the following theorem. On the other hand, we don’t know any sub-linear upper bound for dynamic matrix-vector multiplication over a fixed finite field, even if branching is allowed. It is a very interesting open problem to get super-Ω(log n) lower bounds for any explicit problem over 𝔽_{2} when branching is allowed.

Theorem 11 Let 𝔽 be a finite field. Let the function f : 𝔽^{n} ↦ 𝔽^{m} specialize injectively to some set X_{1} of size l. Then any straight line solution for dynamic evaluation of f over 𝔽 has complexity at least \frac{n−l}{2(l+m)}. Any history independent computation tree solution for dynamic evaluation of f over 𝔽 has complexity at least log \frac{n−l}{2(l+m)}.

Proof. The proof of Theorem 9 carries over, with the following adaptations (and simplifications):

First consider the case of straight line programs. We may take Q = P, since P is a straight line program that is defined for all possible arguments to change-operations. The use of Lemma 5 is replaced by a simple counting argument: when the function g : 𝔽^{n−l} ↦ 𝔽^{|V_{1}|} is injective and 𝔽 is finite, we have that |V_{1}| ≥ n − l by the pigeon hole principle.

In the case of computation trees, we don’t convert the solution to a straight line program. Rather, we let V_{1} be the set of variables appearing in the entire tree corresponding to P_{2}. Then, since the original trees are history independent, |V_{1}| ≤ 2(l + m)2^{d}, yielding the desired lower bound.

2.3 Lower bounds for the integer RAM and the generalized real RAM

We first show how to use Theorem 10 to prove lower bounds in the integer RAM model. Since the integers is a subset of the complex numbers, Theorem 10 implies that the lower bounds holds in the history dependent algebraic computation tree model over the integers (with division disallowed). Now, if an integer RAM solution of a certain complexity exists, we can “fold out” the solution to a solution in the history dependent algebraic computation tree model. Similar unfoldings have been done in several papers, see, for instance, Paul and Simon [PS82]. Unfortunately, in our setting, the unfolded solution may have higher complexity than the original, the problem being indirect addressing: An indirect addressing instruction has to be folded out into a chain of branching nodes, the exact number of nodes depending on the number of indirect writes already performed by the system. However, if we inspect the proofs of Theorems 9 and 10, we see that the lower bound holds even if branching instructions are completely free, as long as the trees remain finite. Thus, the lower bounds we obtained for polynomial functions apply to the integer RAM as well.

To show the lower bound for the generalized real RAM, we have to replace the use of Lemma 5 with results of Ben-Amram and Galil [BAG92] regarding the incompressibility of real numbers using almost continuous operations.

Let c be a positive integer. Let ℱ_{c} be the set of functions f : ℝ^{c} ↦ ℝ, for any k, m > 0, such that for some countable, closed set C ⊂ ℝ^{c}, f is continuous in ℝ^{c} \ C.

As explained above, we just have to generalize the lower bound to history dependent computation trees with the allowed computational operations being ℱ_{c} and the allowed branching instruction being <. If the lower bound holds, even if branching is free (as long as the trees remain finite), the lower bound holds for the generalized real RAM.

Let ℱ_{c}^{∗} be the closure of ℱ_{c} under function composition and aggregation (aggregation combines functions f_{1}, f_{2}, …, f_{k} : ℝ^{m} ↦ ℝ to a vector valued function f = (f_{1}, f_{2}, …, f_{n}) : ℝ^{m} ↦ ℝ^{k}).

Fact 12 (Ben-Amram and Galil [BAG92, Theorem 6]) Let f ∈ ℱ_{c}^{∗}. Then there is a non-empty open set O such that f is continuous in O.

Fact 13 (Ben-Amram and Galil [BAG92, Theorem 10]) Let f ∈ ℱ_{c}^{∗}, f : ℝ^{n} ↦ ℝ^{m} with m < n. Then f is not injective.

By a box in ℝ^{n} we mean a set I_{1} × I_{2} × … × I_{n} where I_{n} is an open interval.

Theorem 14 Given a polynomial function f : ℝ^{n} ↦ ℝ^{m} that specialize injectively to a set of variables of size l. Then, any system of history dependent ℱ_{c}-computation trees solving dynamic evaluation of f has complexity Ω(\frac{n−l}{l+m}).

Proof. Suppose a solution with complexity d is given. As in the proof of Theorem 9, we let

P_{1} : change_{l+1}(z_{1}); ⋯; change_{n}(z_{n−l})
P_{2} : change_{1}(x_{1}); ⋯; change_{l}(x_{l}); y_{1} := query_{1}; ⋯; y_{m} := query_{m}

P = P_{1}; P_{2} is now an ℱ_{c}-computation tree with input variables x_{1}, …, x_{l}, z_{1}, …, z_{n−l}. The leaves of the tree defines a partition of ℝ^{n}. We will show that one of the classes of this partition contains an open set. For this, we only have to show that if all elements of some open set S reaches a branching vertex of the tree, we can find an open subset S′ ⊆ S, so that all elements of S′ take the same branch. Without loss of generality, we can assume that the branching vertex branches according to whether g(x_{1}, …, x_{l}, z_{1}, …, z_{n−l}) > 0, where g is an ℱ_{c}-function. Being open, S contains a subset homeomorphic to ℝ^{n}. This means that Fact 12 applies to functions restricted to S, so we can find a non-empty open subset T ⊆ S so that g is continuous in T. Now, the set U = {x ∈ T |g(x) > 0} is open.

If it is empty, we let S′ = T. If it is non-empty, we let S′ = U. We have now established that we can find a leaf of the tree whose associated subset of ℝ^{n} contains an open set. Let Q be the straight line program we get when we take the path from the root of the tree to this leaf and ignore all branching instructions. Split Q into Q_{1}; Q_{2}, where Q_{1} corresponds to P_{1} and Q_{2} corresponds to P_{2}. Let V_{1} denote the set of variables read by the program Q_{2}. By assumption, |V_{1}| ≤ c(l + m)d.

Q_{1}; Q_{2} computes the same function as P_{1}; P_{2} on an open subset S of ℝ^{n}. If we view S as a subset of ℝ^{n−l} × ℝ^{l}, we can find a box S_{1} ⊂ ℝ^{n−l} and a box S_{2} ⊂ ℝ^{l} so that S_{1} × S_{2} ⊆ S.

Let Ṽ_{1} denote the values of the variables V_{1} after the execution of Q_{1} but before the execution of Q_{2}, and let f̃ denote the function (from X_{1} = {x_{1}, …, x_{l}} ∈ S_{2} to Y = {y_{1}, …, y_{m}}) computed by the program Q_{2}.

Clearly, Ṽ_{1} is a function of a = (a_{1}, a_{2}, …, a_{l}) ∈ S_{1}. Denote this function by g : S_{1} ↦ ℝ^{|V_{1}|}, and observe that g ∈ ℱ_{c}^{∗}. Similarly, f̃ is a function of Ṽ_{1}, since Q_{2} does only depend on a through the intermediate values Ṽ_{1}. Denote this function by h : ℝ^{|V_{1}|} ↦ (S_{2} ↦ ℝ^{m}). Note that, by construction, any function h(y) is a polynomial function defined on an open set S_{2} ⊂ ℝ^{l}. This extends in a unique way to a polynomial function on ℝ^{l}, so we can view h as a function h : ℝ^{|V_{1}|} ↦ (ℝ^{l} ↦ ℝ^{m}). Using that f specializes injectively to X_{1}, we see that F = h ∘ g is injective, and hence also g is injective, We can easily find an injective function g′ in ℱ_{c}^{∗} mapping ℝ^{n−l} to S_{1}, so g ∘ g′ is an injective map from ℝ^{n−l} to ℝ^{|V_{1}|}. By Fact 13, this is only possible if |V_{1}| ≥ n − l.

Combining the two inequalities for V_{1}, we get n − l ≤ |V_{1}| ≤ c(l + m)d, i.e. d = Ω(\frac{n−l}{l+m}).

Using the same reductions as previously, we have: Any generalized real RAM solution for dynamic evaluation of any of the problems matrixvector multiplication, matrix multiplication, matrix adjoint, matrix inverse, determinant and polynomial evaluation has complexity Ω(n) per operation. Any solution for dynamic evaluation of convolution has complexity Ω(\sqrt{n}) per operation.

To get a lower bound for discriminant we consider a weakening of the concept of specializing injectively. The weakening we need is somewhat different from the concept of quasi-injectivity, used in the algebraic case:

Definition 15 Let f : ℝ^{n} ↦ ℝ^{m} be a system of polynomials. Let X = {x_{1}, …, x_{n}} be the set of inputs. Let X_{1} ⊂ X be of size l. f is said to specialize weakly injectively to X_{1} if, for some open subset S ⊆ ℝ^{n−l}, the function F : S ↦ (ℝ^{l} ↦ ℝ^{m}) is injective, where F maps a ∈ S into f_{a}, the function arising from specializing f to the constant vector a on the input set X \ X_{1}.

It is easy to see that the proof of Theorem 14 goes through with “injectively” replaced with “weakly injectively”.

We shall show that discriminant specializes weakly injectively to its first variable. Let X_{1} = {x_{1}} and S ⊆ ℝ^{n−1} be the Cartesian product of n − 1 disjoint intervals. Let f_{a} : ℝ ↦ ℝ denote the function arising from substituting a ∈ S for the inputs in X \ X_{1} = {x_{2}, …, x_{n}}, i.e.

discriminant_{a}(x) = D(a)(−1)^{n−1} ∏_{i=2}^{n}(x − a_{i})^{2},

where D denotes the discriminant function on only n − 1 roots. Note that D(a) is non-zero for all a in S. Observe that if discriminant_{a} and discriminant_{b} are identical functions then the coordinates of a and b must be identical up to a permutation, but by construction, this means that they are equal. We have shown: any generalized real RAM solution for dynamic evaluation of discriminant has complexity Ω(n) per operation.

A similar argument shows the Ω(\sqrt{n}) lower bound for symmetric on the generalized real RAM.

3 Lower bounds for the word RAM

We show a lower bound for dynamic matrix-vector multiplication on the word RAM. The word size of the RAM is denoted w, i.e. each register contains an integer between 0 and 2^{w} − 1 (a word) which is also the range of possible input values. A solution to the problem should work no matter how w and n relate, as long as w ≥ log n. This fact is exploited in the lower bound proof.

The technique used is the communication complexity technique of Miltersen et al [MNSW95] and the proof is in fact a reduction from a variation of the span-problem from that paper. For an exposition of the communication complexity technique and this example in particular, we refer to the book of Kushilevitz and Nisan [KN97].

We present the lower bound proof as a series of reductions. First, assume, to the contrary, that the following holds.

• There is a solution to dynamic matrix-vector multiplication on the word RAM with worst case time o(n) per operation.

In particular

• There is an algorithm which maintains a representation of an n × n word matrix A so that matrix entries can be updated in time t_{1} = o(n) and, given an n-vector x of words, we can compute Ax in time t_{2} = o(n^{2}).

Using perfect hashing to compress the representation, as explained, for instance, in [Mil94], we get

• There is a scheme for representing n×n word matrices so that a matrix can be stored in s = O(t_{1}n^{2}) = o(n^{3}) words so that, given an n-vector x of words, we can compute Ax in time t_{2} = o(n^{2}).

Now consider the following communication game G_{1} between two players, Alice and Bob. Bob gets an n × n matrix A of words and Alice gets an nvector x of words. The object of the game is for Alice to obtain the value of Ax using as few bits of communication as possible. Bob does not need to obtain this information. Using the communication complexity technique on the scheme above (For instance, Kushilevitz and Nisan, Lemma 9.6, page 116), we arrive at a communication protocol:

• There is a protocol for G_{1} where Alice sends O(t_{2} log s) = o(n^{2} log n) bits and Bob sends O(t_{2}w) = o(n^{2}w) bits.

Note that the above protocol works no matter how w and n relate, as this was the case for the original RAM algorithm.

Given w, let p be the smallest prime between 2^{w−1} and 2^{w}. Now consider the following communication game G_{2}: Bob gets n vectors v_{1}, v_{2}, …, v_{n} over 𝔽_{p} (where 𝔽_{p} is the finite field with p elements), Alice gets a single vector x over 𝔽_{p} and they must determine if x is in the span of v_{1}, v_{2}, …, v_{n}. We can derive a protocol for G_{2} from a protocol for G_{1} in the following way: Bob picks an n × n matrix A over 𝔽_{p} so that the kernel of A is exactly the span of v_{1}, v_{2}, …, v_{n}. They now identify 𝔽_{p} with {0, …, p − 1} in the natural way and run the G_{1} protocol on A and x. Alice now knows Ax and can check if it is 0 modulo p and tell Bob if it is. Thus we have:

• There is a protocol for G_{2} where Alice sends o(n^{2} log n) bits and Bob sends o(n^{2}w) bits.

The following lemma now gives us a contradiction, if we put w = Ω(n log n), as we are allowed to do. The same lemma was shown in [MNSW95] for the case p = 2. The proof here is an immediate generalization.

Lemma 16 In any protocol for G_{2}, either Alice sends Ω(nw) bits or Bob sends Ω(n^{2}w) bits.

Proof. For the proof we assume, without loss of generality, that Bob is given exactly n/2 linearly independent vectors.

Consider the communication matrix M of G_{2}, i.e., M has a row for every possible input of Alice (i.e. vectors x) and a column for every possible input of Bob (i.e. sets of vectors V), and M_{x,V} = 1 if and only if x is in the span of V.

A 0-1 matrix M is called (u, v)-rich if at least v columns contain at least u 1-entries. Miltersen et al [MNSW95] showed that if a communication problem has a (u, v)-rich communication matrix and a protocol where Alice sends a bits and Bob sends b bits, then M contains a submatrix of dimensions at least u/2^{a+2} × v/2^{a+b+2} containing only 1-entries.

Using this, it suffices to show

1. M is (p^{n/2}, p^{n^{2}/4})-rich, and

2. M does not contain a 1-monochromatic submatrix of dimensions p^{n/3}× p^{n^{2}/6}.

For 1, notice that every subspace of 𝔽_{p}^{n} of dimension exactly n/2 contains exactly p^{n/2} vectors, and that there are more than p^{n^{2}/4} subspaces of dimension n/2. To see this, we count the number of ways of choosing a basis for such a space (i.e., to choose n/2 independent vectors). There are p^{n}−1 possibilities of choosing the first basis element (different from 0), p^{n} − 2 of choosing the second, p^{n} − 4 of choosing the third etc. Also note that each basis is chosen this way \frac{n}{2}! times. Hence the number of bases is ∏_{i=0}^{n/2−1}(p^{n} − p^{i})/\frac{n}{2}!. Now, each subspace has a lot of bases. By a similar argument, their number is ∏_{i=0}^{n/2−1}(p^{n/2} − p^{i})/\frac{n}{2}!. Hence the total number of subspaces is:

\frac{∏_{i=0}^{n/2−1}(p^{n} − p^{i})}{∏_{i=0}^{n/2−1}(p^{n/2} − p^{i})} = ∏_{i=0}^{n/2−1} \frac{p^{n} − p^{i}}{p^{n/2} − p^{i}} ≥ ∏_{i=0}^{n/2−1} p^{n/2} = p^{n^{2}/4}.

For 2, consider a 1-rectangle with at least p^{n/3} rows. Note that any p^{n/3} vectors span a subspace of 𝔽_{p}^{n} of dimension at least n/3 and that, by a similar argument to the one presented above, the number of subspaces of dimension n/2 that contain a given subspace of dimension n/3 is at most

\frac{∏_{i=0}^{n/6−1}(p^{n} − p^{n/3+i})}{∏_{i=0}^{n/6−1}(p^{n/2} − p^{n/3+i})} = ∏_{i=0}^{n/6−1} \frac{p^{n} − p^{n/3+i}}{p^{n/2} − p^{n/3+i}} ≤ ∏_{i=0}^{n/6−1} p^{n} = p^{n^{2}/6},

as needed.

Using the same reductions as previously, we have shown: Any solution to dynamic matrix-vector multiplication and matrix multiplication on the word RAM has complexity Ω(n). Any solution to dynamic convolution has complexity Ω(\sqrt{n}).

4 Lower bounds based on superconcentrators

For the purposes of our paper, we shall use the following definition of a superconcentrator of depth 2. The equivalence of this definition to the standard definition is due to Meshulam [Mes84].

Definition 17 An n-superconcentrator of depth 2 is a graph G with nodes X ∪ V ∪ Y, where X,V and Y are disjoint, |X| = |Y | = n, and with edges E ⊆ (X × V) ∪ (V × Y) such that for any l, for any X_{1} ⊆ X and for any Y_{1} ⊆ Y with |X_{1}| = |Y_{1}| = l, we have |N(X_{1}) ∩ N(Y_{1})| ≥ l, where N(X_{1}), N(Y_{1}) ⊆ V denote the neighbors to X_{1}, Y_{1}.

Fact 18 (Radhakrishnan and Ta-Shma [RTS97]) The number of edges in an n-superconcentrator of depth 2 is at least Ω(n\frac{log^{2} n}{log log n}).

Definition 19 Let k be an algebraically closed field. Let f : k^{n} ↦ k^{n} be a function. Let X = {x_{1}, …, x_{n}} be the set of inputs, and let Y = {y_{1}, …, y_{n}} be the set of outputs.

f is said to be super-injective, when for every l, for every X_{1} ⊆ X and for every Y_{1} ⊆ Y satisfying that |X_{1}| = |Y_{1}| = l there is a ∈ k^{n−l} such that f_{a} : k^{l} ↦ k^{l} is injective, where f_{a} denotes the function arising from specializing f to the constants a on the inputs X \ X_{1} and ignoring all outputs in Y \ Y_{1}.

Lemma 20 Let k be an algebraically closed field. Let f : k^{n} ↦ k^{n} be a super-injective polynomial function. From any family of straight line programs for dynamic evaluation of f and of complexity d, one may construct an n-superconcentrator of depth 2 and with at most 3dn edges.

Proof. From the dynamic solution for f, define a graph G as follows. The nodes of G is X ∪ V ∪ Y, where V is the variables used in the dynamic solution for f, i.e. we may assume that V = {v_{1}, …, v_{m}}, where m ≤ 2dn. The edges of G is E ⊆ (X × V) ∪ (V × Y) and (x_{i}, v) ∈ E, if the program for change_{i} writes the variable v. Similarly, (v, y_{j}) ∈ E, if the program for query_{j} reads the variable v. Clearly, |E| ≤ 3dn. We shall argue that G is a superconcentrator.

Let l be given, and let X_{1} ⊆ X, Y_{1} ⊆ Y be given such that |X_{1}| = |Y_{1}| = l. Let V_{1} = N(X_{1}) ∩ N(Y_{1}). We need to argue that |V_{1}| ≥ l. (After permutation of indices) we may assume that X_{1} = {x_{1}, …, x_{l}} and Y_{1} = {y_{1}, …, y_{l}}. Use the super-injectivity of f to choose a ∈ k^{n−l} such that f_{a} : k^{l} ↦ k^{l} is injective, where f_{a} denotes the function arising from specializing the inputs (x_{l+1}, …, x_{n}) to the constants a = (a_{1}, …, a_{n−l}) and ignoring all the outputs (y_{l+1}, …, y_{n}).

¿From the dynamic solution for f, construct an off-line solution P = P_{1}; P_{2}; P_{3} for f_{a} as follows

P_{1} : change_{l+1}(a_{1}); ⋯; change_{n}(a_{n−l})
P_{2} : change_{1}(x_{1}); ⋯; change_{l}(x_{l})
P_{3} : y_{1} := query_{1}; ⋯; y_{l} := query_{l}

Let X̃_{1} denote the values of the input variables X_{1} (before the execution of P_{2}), let Ṽ_{1} denote the values of the variables V_{1} after the execution of P_{2} but before the execution of P_{3}, and let Ỹ_{1} denote the values of the output variables Y_{1} (after the execution of P_{3}). Clearly, Ṽ_{1} is a rational function of X̃_{1}. Denote this rational function by g : k^{l} ↦ k^{|V_{1}|}. Similarly, Ỹ_{1} is a rational function of Ṽ_{1}, since the output does only depend on the input through the intermediate values Ṽ_{1}. Denote this rational function by h : k^{|V_{1}|} ↦ k^{l}. We see that f_{a} = h ∘ g. Since f_{a} is injective, so must also g be injective, and by Lemma 5 this is only possible if |V_{1}| ≥ l.

Lemma 20 and Fact 18 together implies the following theorem.

Theorem 21 Let k be an algebraically closed field. Let f : k^{n} ↦ k^{n} be a super-injective polynomial function. Any family of straight line programs for dynamic evaluation of f has complexity Ω(\frac{log^{2} n}{log log n}).

4.1 Lower bound for discrete Fourier transform

It is obvious that a linear map is super-injective if and only if all minors of the corresponding matrix are non-zero. Thus, by Theorem 21, to show the Ω((log n)^{2}/ log log n) lower bound for dynamic dft claimed in Theorem 2 of the introduction, we need to show that this is the case for a large (n^{Ω(1)} × n^{Ω(1)}) submatrix of the Fourier transform matrix. The following lemma accomplishes this.

Lemma 22 Let k be an algebraically closed field of characteristic 0, let ω ∈ k be a primitive n’th root of unity, and let F = (a_{ij}) be the n × n discrete Fourier transform matrix with a_{ij} = ω^{ij}.

Then F contains an l × l submatrix B for some l = Ω( ^{3} \sqrt{\frac{n}{log log n}}) such that all minors of B are nonzero.

Proof. Let l = ⌊ ^{3} \sqrt{ϕ(n)}⌋, where ϕ(n) denotes the Euler phi function, which is also the number of distinct primitive n’th roots of unity. It is known that lim inf_{n→∞} \frac{ϕ(n) ln ln n}{n} = e^{−γ} ≈ 0.56 (see Hardy and Wright [HW54] page 267, theorem 328), so l = Ω( ^{3} \sqrt{\frac{n}{log log n}}) as required.

Let z be a variable and let C(z) be the l × l matrix with the ij’th entry being c_{ij} = z^{ij}. Let B = C(ω) and note that B occurs as the l ×l submatrix in the upper left corner of F.

We show that all minors of B are nonzero. Clearly, each minor of C(z) is a polynomial in z with integer coefficients, and we will later show that no minor of C(z) is the zero-polynomial. Therefore, each minor in C(z) is a nonzero polynomial of degree strictly less than l^{3} ≤ ϕ(n) (assuming that l ≥ 2). This implies that the minors of B = C(ω) are nonzero. To see this, observe that ω is a root of the nth cyclotomic polynomial which has degree ϕ(n) and is irreducible over the field ℚ (see Hungerford [Hun74], page 299, Proposition 8.3). Therefore ω is not root of any polynomial with integer coefficients and of degree strictly smaller than ϕ(n), as k has characteristic 0.

We now show that no minor in the matrix C(z) is the zero-polynomial. Let an m × m minor D in C(z) be given by row-indices i_{1} < ⋯ < i_{m} and column indices j_{1} < ⋯ < j_{m}. By Lemma 23, D = z^{i_{1}j_{1}+···+i_{m}j_{m}} + p(z), where p(z) is either the zero-polynomial or has degree strictly less than i_{1}j_{1} + ⋯ + i_{m}j_{m}.

Lemma 23 Let two sets of m positive integers each be given, namely I containing i_{1} < ⋯ < i_{m} and J containing j_{1} < ⋯ < j_{m}. For any permutation σ of {1, …, m}, let S_{σ} = i_{1}j_{σ(1)} + ⋯ + i_{m}j_{σ(m)}. Then S_{1} > S_{σ} for σ ≠ 1, where 1 denotes the identity permutation.

Proof. Let σ be a permutation on {1, …, l} such that σ ≠ 1. We will argue that by changing σ slightly, we can get a new permutation τ (possibly with τ = 1) such that S_{τ} > S_{σ}, which suffices to prove the lemma.

Since σ ≠ 1, we can find a < b such that σ(a) > σ(b). Define τ to be identical to σ except that τ(a) = σ(b) and τ(b) = σ(a). This implies that S_{τ} = S_{σ} − i_{a}j_{σ(a)} − i_{b}j_{σ(b)} + i_{a}j_{τ(a)} + i_{b}j_{τ(b)} = S_{σ} − i_{a}j_{σ(a)} − i_{b}j_{σ(b)} + i_{a}j_{σ(b)} + i_{b}j_{σ(a)} = S_{σ} + (i_{b} − i_{a})(j_{σ(a)} − j_{σ(b)}) > S_{σ}.

We have established the lower bound claimed in Theorem 2 when the allowed set of change-arguments is the entire field. We show how to establish it when arguments are restricted to an infinite subset S. A specific queryoperation returns a value that is a rational function of the current input values (the function may depend on the sequence of earlier operations). If this function is the correct one when inputs are from S^{n}, Lemma 7 implies that it will be correct in general, except perhaps on some algebraic subset. This subset could be a problem, since superinjectivity just guarantees that there exists an a such that f_{a} is injective, but this particular a may cause division by zero. Fortunately, in the case of dft, we observe that any value of a works. Hence, the lower bound holds with restricted inputs.

References

[AHNR95] A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proc. Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 427–436, 1995.

[BAG91] Amir M. Ben-Amram and Zvi Galil. Lower bounds for data structure problems on RAMs (extended abstract). In Proc. 32nd Annual Symposium on Foundations of Computer Science, pages 622–631, 1991.

[BAG92] Amir M. Ben-Amram and Zvi Galil. On pointers versus addresses. J. Assoc. Comput. Mach, 39:617–648, 1992.

[Eis95] David Eisenbud. Commutative Algebra, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, 1995.

[Fre81] M.L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput., 10:1–10, 1981.

[Fre82] M.L. Fredman. The complexity of maintaining an array and computing its partial sums. J. Assoc. Comput. Mach., 29:250– 260, 1982.

[FS89] M.L. Fredman and M.E. Saks. The cell probe complexity of dynamic data structures. In Proc. Twenty First Annual ACM Symposium on Theory of Computing, pages 345–354, 1989.

[FW93] M.L. Fredman and D.E. Willard. Surpassing the informationtheoretic bound with fusion trees. J. Comput. System Sci., 47:424–436, 1993.

[FW94] M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for mimimum spanning trees and shortest paths. J. Comput. System Sci., 48:533–551, 1994.

[Hag98] Torben Hagerup. Sorting and searching on the Word RAM. In Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 366–398. Springer-Verlag, 1998.

[HF93] H. Hampapuram and M.L. Fredman. Optimal bi-weighted binary trees and the complexity of maintaining partial sums. In Proc. 34th Annual Symposium on Foundations of Computer Science, pages 480–485, 1993.

[Hun74] Thomas W. Hungerford. Algebra, volume 73 of Graduate Texts in Mathematics. Springer-Verlag, 1974.

[HW54] G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. (Third Edition). Oxford University Press, 1954.

[KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.

[Mes84] Roy Meshulam. A geometric construction of a superconcentrator of depth 2. Theoret. Comput. Sci., 32:215–219, 1984.

[Mil94] P.B. Miltersen. Lower bounds for Union-Split-Find related problems on random access machines. In Proc. Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 625–634, 1994.

[MNSW95] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proc. Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 103–111, 1995. To appear in J. Comput. System Sci.

[PS82] W. Paul and J. Simon. Decision trees and random access machines. In Logic and Algorithmic, volume 30 of Monograph. Enseign. Math., pages 331–340. Univ. Genève, 1982.

[RT97] John H. Reif and Stephen R. Tate. On dynamic algorithms for algebraic problems. J. Algorithms, 22:347–371, 1997.

[RTS97] Jaikumar Radhakrishnan and Amnon Ta-Shma. Tight bounds for depth-two superconcentrators. In Proc. 38th Annual Symposium on Foundations of Computer Science, pages 585–594, 1997.

[Sav74] J.E. Savage. An algorithm for the computation of linear forms. SIAM J. Comput., 3:150–158, 1974.

[Sch80] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach., 27:701–717, 1980.

[Win67] S. Winograd. On the number of multiplications required to compute certain functions. Proc. Nat. Acad. Sci. U.S.A., 58:1840– 1842, 1967.

[Win70] S. Winograd. On the number of multiplications necessary to compute certain functions. Comm. Pure Appl. Math., 23:165– 179, 1970.

[Yao85] A.C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput., 14:277–288, 1985.

Recent BRICS Report Series Publications

RS-98-11 Gudmund Skovbjerg Frandsen, Johan P. Hansen, and Peter Bro Miltersen. Lower Bounds for Dynamic Algebraic Problems. May 1998. 30 pp.

RS-98-10 Jakob Pagter and Theis Rauhe. Optimal Time-Space Trade-Offs for Sorting. May 1998. 12 pp.

RS-98-9 Zhe Yang. Encoding Types in ML-like Languages (Preliminary Version). April 1998. 32 pp.

RS-98-8 P. S. Thiagarajan and Jesper G. Henriksen. Distributed Versions of Linear Time Temporal Logic: A Trace Perspective. April 1998. 49 pp. To appear in 3rd Advanced Course on Petri Nets, ACPN ’96 Proceedings, LNCS, 1998.

RS-98-7 Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked Ancestor Problems (Preliminary Version). April 1998. 36 pp.

RS-98-6 Kim Sunesen. Further Results on Partial Order Equivalences on Infinite Systems. March 1998. 48 pp.

RS-98-5 Olivier Danvy. Formatting Strings in ML. March 1998. 3 pp. This report is superseded by the later report BRICS RS-98-12.

RS-98-4 Mogens Nielsen and Thomas S. Hune. Deciding Timed Bisimulation through Open Maps. February 1998.

RS-98-3 Christian N. S. Pedersen, Rune B. Lyngsø, and Jotun Hein. Comparison of Coding DNA. January 1998. 20 pp. To appear in Combinatorial Pattern Matching: 9th Annual Symposium, CPM ’98 Proceedings, LNCS, 1998.

RS-98-2 Olivier Danvy. An Extensional Characterization of Lambda-Lifting and Lambda-Dropping. January 1998.

RS-98-1 Olivier Danvy. A Simple Solution to Type Specialization (Extended Abstract). January 1998. 7 pp.

RS-97-53 Olivier Danvy. Online Type-Directed Partial Evaluation. December 1997. 31 pp. Extended version of an article to appear in Third Fuji International Symposium on Functional and Logic Programming, FLOPS ’98 Proceedings (Kyoto, Japan, April 2– 4, 1998), pages 271–295, World Scientific, 1998.

RS-97-52 Paola Quaglia. On the Finitary Characterization of π-Congruences. December 1997. 59 pp.