Paper by Erik D. Demaine
- Mihai Pǎtraşcu and Erik D. Demaine, “Logarithmic Lower Bounds in the Cell-Probe Model”, SIAM Journal on Computing, volume 35, number 4, 2006, pages 932–963. Special issue of selected papers from the 36th ACM Symposium on Theory of Computing, 2004.
We develop a new technique for proving cell-probe lower bounds on
dynamic data structures. This technique enables us to prove an
amortized randomized Ω(lg n) lower bound per operation for
several data structural problems on n elements, including partial
sums, dynamic connectivity among disjoint paths (or a forest or a
graph), and several other dynamic graph problems (by simple
reductions). Such a lower bound breaks a long-standing barrier of
Ω(lg n / lg lg n)
for any dynamic language membership problem.
It also establishes the optimality of several existing
data structures, such as Sleator and Tarjan's dynamic trees. We
also prove the first Ω(logB n)
lower bound in the
external-memory model without assumptions on the data structure
(such as the comparison model). Our lower bounds also give a
query-update trade-off curve matched, e.g., by several data
structures for dynamic connectivity in graphs. We also prove
matching upper and lower bounds for partial sums when parameterized
by the word size and the maximum additive change in an update.
- This paper is also available from SIAM. This paper is also available as arXiv:cs.DS/0502041 of the Computing Research Repository (CoRR).
- The paper is 32 pages.
- The paper is available in PostScript (653k), gzipped PostScript (256k), and PDF (387k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- DynamicConnectivity_STOC2004 (Lower Bounds for Dynamic Connectivity)
- PartialSums_SODA2004 (Tight Bounds for the Partial-Sums Problem)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2021 by