Unifying the Landscape of Cell-Probe Lower Bounds
Author:
- Mihai PtraşcuMPMihai Ptraşcu
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (3) , 827-847
Abstract
We show that a large fraction of the data-structure lower bounds known today in fact follow by reduction from the communication complexity of lopsided (asymmetric) set disjointness. This includes lower bounds for (i) high-dimensional problems, where the goal is to show large space lower bounds; (ii) constant-dimensional geometric problems, where the goal is to bound the query time for space $O(n\cdot\mathrm{polylog}n)$; and (iii) dynamic problems, where we are looking for a trade-off between query and update time. (In the last case, our bounds are slightly weaker than the originals, losing a $\lg\lg n$ factor.) Our reductions also imply the following new results: (i) an $\Omega(\lg n/\lg\lg n)$ bound for four-dimensional range reporting, given space $O(n\cdot\mathrm{polylog}n)$ (this is quite timely, since a recent result [Y. Nekrich, in Proceedings of the 23rd ACM Symposium on Computational Geometry (SoCG), 2007, pp. 344–353] solved three-dimensional reporting in $O(\lg^2\lg n)$ time, raising the prospect that higher dimensions could also be easy); (ii) a tight space lower bound for the partial match problem, for constant query time; and (iii) the first lower bound for reachability oracles. In the process, we prove optimal randomized lower bounds for lopsided set disjointness.
Keywords
This publication has 45 references indexed in Scilit:
- An information statistics approach to data stream and communication complexityJournal of Computer and System Sciences, 2004
- New Lower Bound Techniques for Dynamic Partial Sums and Related ProblemsSIAM Journal on Computing, 2003
- Optimal Bounds for the Predecessor Problem and Related ProblemsJournal of Computer and System Sciences, 2002
- Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe ModelJournal of Computer and System Sciences, 2002
- On Approximate Nearest Neighbors under l∞ NormJournal of Computer and System Sciences, 2001
- A Generalization of a Lower Bound Technique due to Fredman and SaksAlgorithmica, 2001
- Lower Bounds for Fully Dynamic Connectivity Problems in GraphsAlgorithmica, 1998
- Two-Dimensional and Three-Dimensional Point Location in Rectangular SubdivisionsJournal of Algorithms, 1995
- A lower bound for finding predecessors in Yao's cell probe modelCombinatorica, 1988
- A Functional Approach to Data Structures and Its Use in Multidimensional SearchingSIAM Journal on Computing, 1988