**Reference**:- Lily Chung, Erik D. Demaine, Della 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. **Abstract**:-
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*(*n*,*m*)) time per operation, but any partially retroactive version of that data structure requires*T*(*n*,*m*) ·*m*^{1 − 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*(*n*,*m*)) time per operation can be converted (via the “rollback method”) into a partially retroactive data structure running in*O*(*T*(*n*,*m*) \cdot*m*) time per operation, so our lower bound is tight up to an*m*^{o(1)}factor common in fine-grained complexity. **Comments**:- This paper is also available from LIPIcs.
The full paper is available as arXiv:2211.14664.

**Availability**:- 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.

Last updated July 23, 2024 by Erik Demaine.