Lower bounds for predecessor searching in the cell probe model
From MaRDI portal
Publication:2475409
Recommendations
Cites work
- A lower bound for finding predecessors in Yao's cell probe model
- A strong lower bound for approximate nearest neighbor searching
- Are Bitvectors Optimal?
- Communication Complexity
- Design and implementation of an efficient priority queue
- Ecole d'ete de probabilités de Saint-Flour VII-1977
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Fidelity for Mixed Quantum States
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 2038719 (Why is no real title available?)
- scientific article; zbMATH DE number 1754604 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- scientific article; zbMATH DE number 845841 (Why is no real title available?)
- scientific article; zbMATH DE number 1406113 (Why is no real title available?)
- Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Lower bounds for union-split-find related problems on random access machines
- Mathematical techniques for quantum communication theory
- On data structures and asymmetric communication complexity
- Optimal bounds for the predecessor problem and related problems
- Preserving order in a forest in less than logarithmic time and linear space
- Private vs. common random bits in communication complexity
- Quantum complexities of ordered searching, sorting, and element distinctness
- Should Tables Be Sorted?
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Surpassing the information theoretic bound with fusion trees
- Time-space trade-offs for predecessor search
Cited in
(15)- A lower bound for finding predecessors in Yao's cell probe model
- Optimal bounds for the predecessor problem and related problems
- Optimal bounds for the predecessor problem
- The bit complexity of the predecessor problem
- Time-space trade-offs for predecessor search
- Randomized OBDDs for the most significant bit of multiplication need exponential size
- New limits to classical and quantum instance compression
- Linear algebraic methods in communication complexity
- scientific article; zbMATH DE number 1754604 (Why is no real title available?)
- Pointer chasing via triangular discrimination
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- Cell-probe lower bounds for the partial match problem
- Predecessor on the Ultra-Wide Word RAM
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- Pointer chasing with unlimited interaction
This page was built for publication: Lower bounds for predecessor searching in the cell probe model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2475409)
