On dynamic bit-probe complexity

AbstractThis 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 Ω((lgnlglgn)2). Surpassing Ω(lgn) was listed as the first open problem in a survey by Miltersen.•We prove a bound of Ω(lgnlglglgn) for maintaining partial sums in Z/2Z. Previously, the known bounds were Ω(lgnlglgn) and O(lgn).•We prove a surprising and tight upper bound of O(lgnlglgn) 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 Ω(lgnlglgn) was a central open problem in cell-probe complexity