Paper by Erik D. Demaine

Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch, “Lower Bounds on Retroactive Data Structures”, in Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), LIPIcs, Seoul, Korea, December 19–21, 2022, 32:1–32:13.

We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in O(T(nm)) time per operation, but any partially retroactive version of that data structure requires T(nm) · m1 − o(1) worst-case time per operation, where n is the size of the data structure at any time and m is the number of operations. Any data structure with operations running in O(T(nm)) time per operation can be converted (via the “rollback method”) into a partially retroactive data structure running in O(T(nm) \cdot m) time per operation, so our lower bound is tight up to an mo(1) factor common in fine-grained complexity.

This paper is also available from LIPIcs.

The full paper is available as arXiv:2211.14664.

The paper is available in PDF (723k).
See information on file formats.
[Google Scholar search]

Related papers:
RetroactiveSeparation_SWAT2018 (Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures)
FullyRetroactive_WADS2015 (Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing)
Retroactive_TALG (Retroactive Data Structures)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.