Lower bounds for predecessor searching in the cell probe model

DOI10.1016/j.jcss.2007.06.016zbMath1133.68017OpenAlexW2038255135MaRDI QIDQ2475409

Yanyan Li

Publication date: 11 March 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.016

zbMATH Keywords

data structureslower boundscell probe modelpredecessor searching problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (5)

New Limits to Classical and Quantum Instance Compression ⋮ Linear algebraic methods in communication complexity ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ Unnamed Item ⋮ Pointer chasing via triangular discrimination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong lower bound for approximate nearest neighbor searching
• A lower bound for finding predecessors in Yao's cell probe model
• Private vs. common random bits in communication complexity
• Preserving order in a forest in less than logarithmic time and linear space
• Ecole d'ete de probabilités de Saint-Flour VII-1977
• On data structures and asymmetric communication complexity
• Surpassing the information theoretic bound with fusion trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal bounds for the predecessor problem and related problems
• Quantum complexities of ordered searching, sorting, and element distinctness
• Lower bounds for union-split-find related problems on random access machines
• Time-space trade-offs for predecessor search
• Are Bitvectors Optimal?
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Mathematical techniques for quantum communication theory
• Should Tables Be Sorted?
• Design and implementation of an efficient priority queue
• Fidelity for Mixed Quantum States
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Communication Complexity
• Interaction in quantum communication and the complexity of set disjointness
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

This page was built for publication: Lower bounds for predecessor searching in the cell probe model