On the cell probe complexity of polynomial evaluation (note)
Peter Bro Miltersen y Aarhus University and University of Warwick
We consider the cell probe complexity of the polynomial evaluation problem with preprocessing of coe cients, for polynomials of degree at most n over a nite eld K . We show that the trivial cell probe algorithm for the problem is optimal if K is su ciently large compared to n. As an application, we give a new proof of the fact that P 6= incr-TIME(o(log n= log log n)).
Abstract
1 Introduction
Let K be a eld. We consider the polynomial evaluation problem with preprocessing of coe cients. This problem is as follows: Given a polynomial f (X ) 2 K X ], preprocess it, so that later, for any eld element a 2 K , f (a) can be computed e ciently. It is a classical problem in the theory of algebraic complexity and has been intensively investigated in the model of arithmetic straight line programs. In this model, a solution for the polynomials of degree at most n is given by two objects: A map from the set of polynomials of degree at most n into K s, where s is any integer, called the preprocessing map. This maps associates with each polynomial f (X ) a vector (y1 ; y2 ; : : : ; ys ), the result of preprocessing f (X ). An arithmetic straight line program P with inputs x; y1 ; y2 ; : : : ; ys, i.e. a sequence of instructions
wi gi2f1;:::;tg ; where ui ; wi 2 K fx; y1 ; ys; : : : ; ys; v1 ; v2 ; : : : vi?1 g and i 2 f+; ?; g. The program P de nes a function P : K 1+s ! K in the natural way (the value of the function being the value of the variable vt ). The solution ( ; P ) is a correct
i
fvi := ui
This work was supported by a grant from the Danish Natural Science Research Council. It was partially supported by the ESPRIT II Basic Research Actions Program of the European Community under contract No. 7141 (project ALCOM II). y Correspondence to: Peter Bro Miltersen, University of Warwick, Department of Computer Science, Coventry CV4 7AL, U.K. Email: pbmilter@dcs.warwick.ac.uk or pbmiltersen@daimi.aau.dk
1
solution for the polynomial evaluation problem if P (a; (f (X ))) = f (a) for all f (X ) and a. The complexity of the solution is t, the number of steps in P . An obvious solution is to let be de ned by (a0 + a1 X + a2 X 2 + : : : + an X n ) = (a0 ; a1 ; : : : ; an ) i.e. refrain from preprocessing, and let P evaluate the polynomial using Horner's rule, i.e.
v1 v2 v3 v4
:= := := :=
yn x v1 + yn?1 v2 x v3 + yn?2
v2n := v2n?1 + y0 with a complexity of 2n. This is not optimal for K = R: Pan 11] gives a scheme with complexity b 32n c + 2 for K = R. His scheme is almost optimal, Belaga 4] shows that any correct scheme for K = R has complexity at least b 32n c + 1. For a
survey of these, and similar, more recent, results, see Knuth 7, pp. 470-479]. In this paper we consider the problem for K being a nite eld. Since the lower bounds above are proved in the context of algebraic independence theory, there is no way to extend them to this situation. If K is a nite eld we might also note that the arithmetic straight line program model seems unreasonable weak, since we in that case can represent the elements of K by small integers and use the full power of a random access machine, e.g. branching, indirect addressing and an extended instruction set, to solve the problem. This changes the problem somewhat. For instance, in order to get a non-trivial problem we must put a bound on s, the number of indices in (f (X )), since we could otherwise, in the case where e.g. K = Zp , de ne (f (X )) = (f (0); f (1);f (2); : : : ; f (p ? 1)) and \compute" f (a) for any value of a with a single table look up, using indirect addressing. The precise model in which we consider the problem in this paper is the cell probe model, which for our purposes can be regarded as a strong, non-uniform version of the random access machine model. Previously, the cell probe model has been studied mainly for set problems, such at the problems of storing a set S f1; : : : ; mg, using few (e.g. O(jS j)) cells, each containing an element from f1; : : : ; mg, so that membership queries \Is i 2 S ?" 13, 5] or rank queries \What is jS \ f1; : : : ; igj?" 2, 1, 9] can be answered e ciently. In the cell probe model, a solution with size bound s for the polynomial evaluation problem for polynomials of degree at most n is given by the following objects: As in the straight line model, a preprocessing map from the set of polynomials of degree at most n into K s. For each a 2 K a decision tree Ta over K s. This is a rooted tree with each internal node having jK j sons. Each node is labeled with an integer between 1 and s. The out-going edges from each node are labeled with elements of K , each possible value appearing exactly once. The leaves are labeled with elements from K .
2
Given a vector y 2 K s, we can compute a value Ta (y) by the following procedure: We start in the root of Ta and read its label i. We proceed to a new node by following the edge with label yi , and read the label of this node, etc. We continue this until reaching a leaf, the value read there is Ta (y). A cell probe algorithm is correct if Ta ( (f (X )) = f (a) for all f (X ) and a. Its complexity is the depth of the deepest tree. Note that the cell probe model only makes sense for K a nite eld, since if K is in nite, we can let be an injection K n ! K , giving a complexity of 1. If s n + 1, an upper bound on the complexity of the problem is n + 1, by the algorithm which stores a polynomial as its coe cients and reads them all when evaluating. We are interested in knowing if this is optimal. We prove the following result. Theorem 1 Let K be a nite eld. Any size bound s cell probe algorithm solving the problem for polynomials of degree at most n has complexity at least min(n + 1; log jK j ? log n ) log s Thus, if s is reasonably small (e.g. s = nO(1) ), and K is su ciently large compared to n (log jK j >> n log n), the trivial cell probe algorithm is optimal. We don't have any lower bounds for smaller values of jK j, but neither do we know of any scheme beating the trivial upper bound for any value of jK j and n with n; s = o(jK j). We conjecture that the lower bound holds for smaller values of jK j as well, i.e. that polynomial evaluation in general is access infeasible 8]. As an application, we consider lower bounds for dynamic language membership problems. The class of dynamic language membership problems is a general class of dynamic problems, considered by Miltersen, Subramanian, Vitter and Tamassia 10]. A problem in this class is given by a language L f0; 1g . We are supposed to implement a data type L-MEMBER containing a string x 2 f0; 1g with three kinds of operations: init(n). This operation initializes x to 0n . change(i; a). This operation changes the i'th component of x to a. query. This operation returns true if x 2 L, false otherwise. Many naturally occurring problems, for instance dynamic graph problems, can be phrased as dynamic language membership problems. For a time bound t(n), the complexity class incr-TIME(t(n)) is the class of languages L for which L-MEMBER has an implementation on a random access computer 3], i.e. a unit cost random access machine where each machine word stores an integer, polynomially bounded in n, so that init(n) can be done in time nO(1) and change and query can be done in time t(n) (with n = jxj). Because polynomial initialization time is allowed and no restrictions on the amount of memory used by the implementation is made, the de nition is robust against reasonable changes in the instruction set of the random access computer, since we can make tables of required instructions during initialization. Clearly, for any time bound t(n) bounded by a polynomial, incr-TIME(t(n)) is included in P, the class of languages which can be recognized in polynomial time, but it is an open problem if P = incr-TIME(O(log n= log log n)). It follows from a lower bound on dynamic pre x problems by Fredman and Saks 6], using the time stamp method, that P 6= incr-TIME(o(log n= log log n)). We give a completely di erent (and somewhat easier) proof of this fact, by giving a lower bound for a polynomial time problem related to polynomial evaluation.
3
The proof, which is not di cult, uses the technique of reduction from communication problems ( rst used implicitly by Ajtai 1], made explicit by Miltersen 8, 9]), together with standard techniques in communication complexity 12], modi ed to non-binary protocols. In the following, K is a xed nite eld with jK j = k. Consider the following communication game between two players, Alice and Bob. Alice is given a 2 K . Bob is given a polynomial f (X ) 2 K X ] of degree at most n. The object of the game is to let Alice determine the value of f (a) through communication with Bob. The communication is structured in the following way: Alice chooses her messages from f1; : : : ; sg, Bob chooses his messages from f1; : : : ; kg and the communication is strictly alternating, with Alice sending the rst message. The complexity is the worst case number of rounds required in an optimal protocol before Alice is able to give the correct answer. Lemma 2 If there is a cell probe algorithm with size bound s and complexity t for the polynomial evaluation problem, then the complexity of the communication game is at most t. Proof We construct a communication protocol using the cell probe algorithm. s Suppose Alice is given a and Bob is given f (X ). Bob computes (f (X )) 2 K , but does not send anything yet. Then Alice simulates the decision tree Ta by sending Bob requests for the cells she wants to read in (f (X )). Bob sends the content of the cell in question back. This is repeated until a leaf in the decision tree is reached and Alice knows the answer, i.e. for at most t rounds.
2 The proof
2 We now show a lower bound for the communication problem. In the following lemma, we consider a general communication problem h : A B ! C , where Alice is given a 2 A, Bob is given b 2 B and the objective of the game is to let Alice nd h(a; b). Again, Alice chooses her messages from f1; : : : ; sg and Bob chooses his from f1; : : : ; kg. Lemma 3 If a communication problem h : A B ! C has a t round protocol, then there is A0 A and B 0 B so that jA0j jAj=st and jB 0 j jB j=kt and so that 8 x 2 A0 8 y; z 2 B 0 : h(x; y) = h(x; z ): Proof By induction in t. The lemma clearly holds for t = 0, since if Alice can announce the answer without communicating with Bob, the function can only depend on her input. Now assume that it holds for t, and we will show it for t + 1. Let a communication problem h with a t +1 protocol P be given. For 2 f1; : : : ; sg, let A be those x 2 A for which Alice sends as a rst message when given x as input. Fix , so that jA j jAj=s. For 2 f1; : : : ; kg, let B be those y 2 B for which Bob send as the rst message if was the rst message received. Fix , so that jB j jB j=k. The communication problem h, restricted to A B has a t round protocol P 0 , doing the following: Simulate P from the second round on, pretending that in the rst round, Alice sent to Bob and Bob sent to Alice. By the induction hypothesis, we can nd A0 and B 0 of the appropriate size. 2
4
Find A K and a subset B of the polynomials over K with degree at most n with the properties stated in Lemma 3, i.e.
Proof 0 of Theorem 1 Assume the communication game has a t round protocol. 0
jB 0j kn =kt = kn ?t
+1 +1
jA0j k=st ;
and
Since two di erent polynomials of degree at most n over a eld can agree on at most n points, we have that
8 x 2 A0 8 f (X );g(X ) 2 B 0 : f (x) = g(x): jA0j n _ jB 0j 1
so and
k=st n _ kn+1?t 1
By Lemma 2, this is also a lower bound on the cell probe complexity of the original problem.
? log t min(n + 1; log klog s n ):
2
We need a slightly modi ed version of Theorem 1 for the application in this section. For a 2 Zm , the ring of integers modulo m, we say that a is positive if a 2 f0; : : : ; dm=2e ? 1g. We consider a modi ed polynomial evaluation problem, where we only have to determine if f (a) is positive. Theorem 4 Let K = Zp , p 3 a prime. Any size bound s cell probe algorithm solving the modi ed polynomial evaluation problem for polynomials of degree at most n has complexity at least n+ log min( 2 log 1 ; log p ? s n ): p log Proof We note that if, for n + 1 di erent points ai , there are r polynomials which on each ai agree on whether their value is positive or not, then r dp=2en+1 . Using this fact, we proceed as in the proof of Theorem 1. We now de ne a language L f0; 1g . We let L\f0; 1gn = ; unless n = mdlog me+ m for some integer m. Let x be a string of length mdlog me + m. The rst mdlog me bits of x are interpreted as the binary notation of the coe cients of a degree m ? 1 polynomial f (X ) over the ring Zm . If the last m bits do not have the form 0a 10m?a?1 , then x 62 L. Otherwise x 2 L if and only if f (a) is positive. Clearly, L 2 P . log n Theorem 5 L 62 incr-TIME(o( log log n )).
3 Application to dynamic problems
2
5
Proof The method is similar to the lower bound proof for the Union-Split-Find
problem in 9]. Suppose an implementation on a random access computer of the dynamic language membership problem for L is given, with the complexity of the change and query operations being o(log n= log log n). Let p be su ciently large prime. Perform the init(pdlog pe + p) operation. The content of any memory location now has to bounded by a polynomial in p until the next init operation. These values include the values used for indirect addressing. We will not perform any more init operations, so in the rest of the proof, we can identify the set of possible states of the random access memory (the memory images) of the implementation with f1; : : : ; mgm , where m = pO(1) (it is convenient for our proof that only a polynomial number of cells can be accessed, but it is possible to modify the proof to not take advantage of this fact. This would give a lower bound in a stronger model, the decision assignment tree model 6, 9]). We now describe a cell probe algorithm ( ; fTa g) for the problem of evaluating polynomials in Zp X ] of degree at most dlog pe2 . Let f (X ) be such a polynomial. Starting from the initialized memory image M0 2 f1; : : : ; mgm , we perform a sequence of dlog pe3 change operations, making the rst pdlog pe bits of x into a representation of f (X ). Let the resulting memory image be Mf 2 f1; : : : ; mgm . By the assumption on the complexity of the change operations, M0 and Mf di er on at most r = dlog pe4 indices. Let these indices be a1 ; a2 ; : : : ; ar and let the new content of ai be di . We need the following fact, due to Fredman, Komlos and Szemeredi 5]: Let m be an integer. There is a scheme for storing sets S f1; : : : ; mg f1; : : : ; mg using O(jS j) cells, each containing an element in f1; : : : ; mg, so that for each j , the query \Is (j; x) in S for some x, and if so, return such an x" can be answered using O(1) probes. We store the set S = f(ai ; di )g using this scheme. The structure uses O(r) cells, each containing an integer between 1 and m. Since m = pO(1) , we can code the content of each cell as O(1) elements of Zp using any code we might like. By concatenating these codes, this gives us a vector in (Zp )O(r) . We de ne (f (X )) to be this vector. We now show that over this structure, f (X ) can be evaluated more e ciently by a family of decision trees than Theorem 4 permits. In order to evaluate f (a), we would like to run the operations change(pdlog pe + 1 + a; 1); query on Mf since this would provide the answer. However, instead of Mf , we only have the structure containing the di erence between M0 and Mf at our disposal. We simulate performing the operations as follows: Each time we want to write the value d in a memory location i, we make a private note that the new content of location i is d. If we want to read a memory location a, we rst see if it appears in our private notes. If it does not, we look it up in the encoding of S . If it does not appear there, we know that its content is the same as it was in M0 . Changing and examining our private notes do not use (f (X )), i.e. these actions can be hardwired into the decision tree, and so can the necessary knowledge about M0 . Each lookup requires only a constant number of probes, i.e. the total number of probes required to evaluate f (X ) on any point is o(log p= log log p) by the assumption on the complexity of change and query. But according to Theorem 4, the number of probes required is at least 2 pe2 + p min( dlog log p 1 ; loglog? log(dlog 4p)e ) ) = (log p= log log p); 2 O(dlog pe a contradiction.
2
6
Acknowledgements
I would like to thank Vlado Danc k, Gudmund S. Frandsen, Thore Husfeldt, and Mike Paterson, for helpful discussions.
References
1] M. Ajtai, A lower bound for nding predecessors in Yao's cell probe model, Combinatorica 8 (1988) 235-247. 2] M. Ajtai, M. Fredman, J. Komlos, Hash functions for priority queues, in: Proc. 24th Ann. IEEE Symp. on Foundations of Computer Science (1983) 299-303. 3] D. Angluin, L.G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. System Sci. 18 (1979) 155-193. 4] E.G. Belaga, Evaluation of polynomials of one variable with preliminary processing of the coe cients, Problemy Kibernet. 5 (1961) 7-15. 5] M.L. Fredman, J. Komlos, E. Szemeredi, Storing a sparse table with O(1) worst case access time, J. Assoc. Comput. Mach. 31 (1984) 538-544. 6] M.L. Fredman, M.E. Saks, The cell probe complexity of dynamic data structures, in: Proc. 21st Ann. ACM Symp. on Theory of Computing (1989) 345354. 7] D.E. Knuth, The Art of Computer Programming, Vol. II: Seminumerical Algorithms (Addison-Wesley, Reading, MA, 2nd ed., 1980). 8] P.B. Miltersen, The bit probe complexity measure revisited, in: Proc. 10th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 665 (Springer, Berlin, 1993) 662-671. 9] P.B. Miltersen, Lower bounds for Union-Split-Find related problems on random access machines, to appear in: Proc. 26th Ann. ACM Symp. on Theory of Computing (1994). 10] P.B. Miltersen, S. Subramanian, J.S. Vitter, R. Tamassia, Complexity models for incremental computation, Theoretical Computer Science, to appear. 11] V. Ya. Pan, Methods of computing values of polynomials, Russian Math. Surveys 21 (1) (1966) 105-136. 12] A.C. Yao, Some complexity questions related to distributive computing, in: Proc. 11th Ann. ACM Symp. on Theory of Computing (1979) 209-213. 13] A.C. Yao, Should tables be sorted?, J. Assoc. Comput. Mach. 28 (1981) 615628.
7