Higher Cell Probe Lower Bounds for Evaluating Polynomials

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 δ u )) for dynamic data structures for polynomial evaluation over a finite field F of size Ω(n 2 ). Here t q 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 δ u, t q } = Ω(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.

Authors

• Kasper Green Larsen

Keywords

• Data structures
• Polynomials
• Probes
• Encoding
• Error probability
• Data models
• Complexity theory
• Lower Bound
• Data Structure
• State Structures
• Structural Dynamics
• Polynomial Of Degree
• Finite Field
• Constant Probability
• Query Time
• Time Constant
• Kinetic Rate
• Set Of Cells
• Input Size
• Structural Evaluation
• Incorrect Answers
• Complex Communication
• Random Bits
• Space Of Polynomials
• Decoding Procedure
• Hardness Distribution
• Worst-case Error
• cell probe model
• lower bounds