Document Open Access Logo

Lower Bounds on Retroactive Data Structures

Authors Lily Chung , Erik D. Demaine , Dylan Hendrickson , Jayson Lynch

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.32.pdf
  • Filesize: 0.76 MB
  • 12 pages

Document Identifiers

Author Details

Lily Chung
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Dylan Hendrickson
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Jayson Lynch
  • Cheriton School of Computer Science, University of Waterloo, Canada

Acknowledgements

This work was initiated during open problem solving in the MIT class on Advanced Data Structures (6.851) in Spring 2021. We thank the other participants of that class - in particular, Joshua Ani, Josh Brunner, and Naveen Venkat - for related discussions and providing an inspiring atmosphere. We also thank Michael Coulombe for helpful pointers regarding time travel.

Cite AsGet BibTex

Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Lower Bounds on Retroactive Data Structures. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.32

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)⋅m) time per operation, so our lower bound is tight up to an m^o(1) factor common in fine-grained complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cell probe models and lower bounds
Keywords
  • Retroactivity
  • time travel
  • rollback
  • fine-grained complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson, Mohammad Bavarian, and Giulio G. Giusteri. Computability theory of closed timelike curves. Technical Report TR16-146, Electronic Colloquium on Computational Complexity, 2016. URL: https://eccc.weizmann.ac.il/report/2016/146, URL: http://arxiv.org/abs/TR16-146.
  2. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584-596, 2007. Google Scholar
  3. Harry Buhrman, Subhasree Patro, and Florian Speelman. A framework of quantum Strong Exponential-Time Hypotheses. In Markus Bläser and Benjamin Monmege, editors, Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, volume 187 of LIPIcs, pages 19:1-19:19, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.19.
  4. Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. Nearly optimal separation between partially and fully retroactive data structures. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, pages 33:1-33:12, Malmö, Sweden, June 2018. Google Scholar
  5. Erik D. Demaine, John Iacono, and Stefan Langerman. Retroactive data structures. ACM Transactions on Algorithms, 3(2): Article 13, May 2007. Google Scholar
  6. Erik D. Demaine, Tim Kaler, Quanquan Liu, Aaron Sidf ord, and Adam Yedidia. Polylogarithmic fully retroactive priority queues via hierarchical checkpointing. In Proceedings of the 14th International Symposium on Algorithms and Data Structures, pages 263-275, Victoria, Canada, August 2015. Google Scholar
  7. James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. Google Scholar
  8. Ari Freund. Improved subquadratic 3SUM. Algorithmica, 77(2):440-458, 2017. URL: https://doi.org/10.1007/s00453-015-0079-6.
  9. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry: Theory and Applications, 5(3):165-185, 1995. Google Scholar
  10. Yoav Giora and Haim Kaplan. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Transactions on Algorithms, 5(3): Article 28, July 2009. URL: https://doi.org/10.1145/1541885.1541889.
  11. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. Journal of the ACM, 65(4):22:1-22:25, 2018. URL: https://doi.org/10.1145/3185378.
  12. Monika Henzinger, Sebastian Krinninger, Danupon Na Nongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual Symposium on the Theory of Computing, pages 21-30, Portland, OR, June 2015. Google Scholar
  13. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  14. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, pages 3447-3487, Rio de Janeiro, Brazil, 2018. World Scientific. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact