Abstract-In this paper, we study the cell probe complexity of evaluating an n-degree polynomial P over a finite field F of size at least n 1+Ω(1) . More specifically, we show that any static data structure for evaluating P (x), where x ∈ F, must use Ω(lg |F|/ lg(Sw/n lg |F|)) cell probes to answer a query, where S denotes the space of the data structure in number of cells and w the cell size in bits. This bound holds in expectation for randomized data structures with any constant error probability δ < 1/2. Our lower bound not only improves over the Ω(lg |F|/ lg S) lower bound of Miltersen [TCS'95], but is in fact the highest static cell probe lower bound to date: For linear space (i.e. S = O(n lg |F|/w)), our query time lower bound simplifies to Ω(lg |F|), whereas the highest previous lower bound for any static data structure problem having d different queries is Ω(lg d/ lg lg d), which was first achieved by Pǎtraşcu and Thorup [SICOMP'10]. We also use the recent technique of Larsen [STOC'12] to show a lower bound of tq = Ω(lg |F| lg n/ lg(wtu/ lg |F|) lg(wtu)) for dynamic data structures for polynomial evaluation over a finite field F of size Ω(n 2 ). Here tq denotes the expected query time and tu the worst case update time. This lower bound holds for randomized data structures with any constant error probability δ < 1/2. This is only the second time a lower bound beyond max{tu, tq} = Ω(max{lg n, lg d/ lg lg d}) has been achieved for dynamic data structures, where d denotes the number of different queries and updates to the problem. Furthermore, it is the first such lower bound that holds for randomized data structures with a constant probability of error.
The lower bound in REF actually holds for nondeterministic cell probes, i.e. certificates.
Higher Cell Probe Lower Bounds for Evaluating Polynomials
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
Mathematics Computer Science