On dynamic bit-probe complexity

Mihai Pa ̌traşcu, Corina E. Tarniţa ̌

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

This work present several advances in the understanding of dynamic data structures in the bit-probe model: •We improve the lower bound record for dynamic language membership problems to Ω ((frac(lg n, lg lg n))2). Surpassing Ω (lg n) was listed as the first open problem in a survey by Miltersen.•We prove a bound of Ω (frac(lg n, lg lg lg n)) for maintaining partial sums in Z / 2 Z. Previously, the known bounds were Ω (frac(lg n, lg lg n)) and O (lg n).•We prove a surprising and tight upper bound of O (frac(lg n, lg lg n)) for the greater-than problem, and several predecessor-type problems. We use this to obtain the same upper bound for dynamic word and prefix problems in group-free monoids. We also obtain new lower bounds for the partial-sums problem in the cell-probe and external-memory models. Our lower bounds are based on a surprising improvement of the classic chronogram technique of Fredman and Saks [Michael L. Fredman, Michael E. Saks, The cell probe complexity of dynamic data structures, in: Proc. 21st ACM Symposium on Theory of Computing STOC, 1989, pp. 345-354], which makes it possible to prove logarithmic lower bounds by this approach. Before the work of M. Pa ̌traşcu and Demaine [Mihai Pa ̌traşcu, Erik D. Demaine, Logarithmic lower bounds in the cell-probe model, SIAM Journal on Computing 35 (4) (2006) 932-963. See also SODA'04 and STOC'04], this was the only known technique for dynamic lower bounds, and surpassing Ω (frac(lg n, lg lg n)) was a central open problem in cell-probe complexity.

Original languageEnglish (US)
Pages (from-to)127-142
Number of pages16
JournalTheoretical Computer Science
Volume380
Issue number1-2
DOIs
StatePublished - Jun 21 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Bit-probe complexity
  • Cell-probe complexity
  • Lower bounds

Fingerprint Dive into the research topics of 'On dynamic bit-probe complexity'. Together they form a unique fingerprint.

  • Cite this