Higher Cell Probe Lower Bounds for Evaluating Polynomials
Kasper Green Larsen · 2012
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 n1+Ω(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 δu)) for dynamic data structures for polynomial evaluation over a finite field F of size Ω(n2). Here tqdenotes the expected query time and tu the worst case update time. This lower bound holds for randomized data structures with any constant error probability δu, 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.