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 Ω ((frac(lg n, lg lg n))²). 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.