AbstractWe give a number of new lower bounds in the cell probe model with logarithmic cell size, which entails the same bounds on the random access computer with logarithmic word size and unit cost operations.
We study the signed prefix sum problem: given a string of length n of 0s and signed 1s, compute the sum of its ith prefix during updates. We show a lower bound of Omega(log n/log log n) time per operations, even if the prefix sums are bounded by log n/log log n during all updates. We also show that if the update time is bounded by the product of the worst-case update time and the answer to the query, then the update time must be Omega(sqrt(log n/log log n)).
These results allow us to prove lower bounds for a variety of seemingly unrelated dynamic problems. We give a lower bound for the dynamic planar point location in monotone subdivisions of Omega(log n/log log n) per operation. We give a lower bound for dynamic transitive closure on upward planar graphs with one source and one sink of Omega(log n/(log log n)2) per operation. We give a lower bound of Omega(sqrt(log n/log log n)) for the dynamic membership problem of any Dyck language with two or more letters. This implies the same lower bound for the dynamic word problem for the free group with k generators. We also give lower bounds for certain range searching variants and for the dynamic prefix majority and prefix equality problems.
Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: cell probe model, lower bounds, dynamic graph algorithms, Dyck languages
Selected references
- Arne Andersson. Sublogarithmic searching without multiplications. In 36th Annual Symposium on Foundations of Computer Science, pages 655-663, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 427-436, Las Vegas, Nevada, 29 May-1 June 1995.
- Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn. Dynamic point location in general subdivisions. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 250-258, Orlando, Florida, 27-29 January 1992.
- Gudmond Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. In 34th Annual Symposium on Foundations of Computer Science, pages 470-479, Palo Alto, California, 3-5 November 1993. IEEE.
- Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 345-354, Seattle, Washington, 15-17 May 1989.
- Peter Bro Miltersen. Lower bounds for Union-Split-Find related problems on random access machines. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 625-634, Montréal, Québec, Canada, 23-25 May 1994.
- Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 103-111, Las Vegas, Nevada, 29 May-1 June 1995.
- Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130(1):203-236, 1 August 1994.
- Franco P. Preparata and Roberto Tamassia. Fully dynamic point location in a monotone subdivision. SIAM Journal on Computing, 18(4):811-830, August 1989.
- Roberto Tamassia and Franco P. Preparata. Dynamic maintenance of planar digraphs, with applications. Algorithmica, 5:509-527, 1990.
- Andrew Chi-Chih Yao. Should tables be sorted? Journal of the ACM, 28(3):615-628, July 1981.