On dynamic bit-probe complexity
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 Omega((lg n / lg lg n)(2)). Surpassing Omega(lg n) was listed as the first open problem in a survey by Miltersen. We prove a bound of Omega(lg n / lg lg n) for maintaining partial sums in Z/2Z. Previously, the known bounds were Omega((lg n / lg lg n) and We prove a surprising and tight upper bound of O(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. Patrascu and Demaine [Mihai Patrascu, 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 W(lg n / lg lg n) was a central open problem in cell-probe complexity. (C) 2007 Elsevier B.V. All rights reserved.
bit-probe complexity lower bounds cell-probe complexity