Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures

Authors Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu



PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.33.pdf
  • Filesize: 498 kB
  • 12 pages

Document Identifiers

Author Details

Lijie Chen
  • Massachusetts Institute of Technology
Erik D. Demaine
  • Massachusetts Institute of Technology
Yuzhou Gu
  • Massachusetts Institute of Technology
Virginia Vassilevska Williams
  • Massachusetts Institute of Technology
Yinzhan Xu
  • Massachusetts Institute of Technology
Yuancheng Yu
  • Massachusetts Institute of Technology

Cite AsGet BibTex

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 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.33

Abstract

Since the introduction of retroactive data structures at SODA 2004, a major unsolved problem has been to bound the gap between the best partially retroactive data structure (where changes can be made to the past, but only the present can be queried) and the best fully retroactive data structure (where the past can also be queried) for any problem. It was proved in 2004 that any partially retroactive data structure with operation time T_{op}(n,m) can be transformed into a fully retroactive data structure with operation time O(sqrt{m} * T_{op}(n,m)), where n is the size of the data structure and m is the number of operations in the timeline [Demaine et al., 2004]. But it has been open for 14 years whether such a gap is necessary. In this paper, we prove nearly matching upper and lower bounds on this gap for all n and m. We improve the upper bound for n << sqrt m by showing a new transformation with multiplicative overhead n log m. We then prove a lower bound of min {n log m, sqrt m}^{1-o(1)} assuming any of the following conjectures: - Conjecture I: Circuit SAT requires 2^{n - o(n)} time on n-input circuits of size 2^{o(n)}. This conjecture is far weaker than the well-believed SETH conjecture from complexity theory, which asserts that CNF SAT with n variables and O(n) clauses already requires 2^{n-o(n)} time. - Conjecture II: Online (min,+) product between an integer n x n matrix and n vectors requires n^{3 - o(1)} time. This conjecture is weaker than the APSP conjectures widely used in fine-grained complexity. - Conjecture III (3-SUM Conjecture): Given three sets A,B,C of integers, each of size n, deciding whether there exist a in A, b in B, c in C such that a + b + c = 0 requires n^{2 - o(1)} time. This 1995 conjecture [Anka Gajentaan and Mark H. Overmars, 1995] was the first conjecture in fine-grained complexity. Our lower bound construction illustrates an interesting power of fully retroactive queries: they can be used to quickly solve batched pair evaluation. We believe this technique can prove useful for other data structure lower bounds, especially dynamic ones.

Subject Classification

ACM Subject Classification
  • Theory of computation → Lower bounds and information complexity
Keywords
  • retroactive data structure
  • conditional lower bound

Metrics

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

References

  1. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, pages 477-486, 2016. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 41-50, New York, NY, USA, 2015. ACM. Google Scholar
  3. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 434-443, 2014. Google Scholar
  4. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584-596, 2007. Google Scholar
  5. Guy E. Blelloch. Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 894-903, 2008. Google Scholar
  6. Timothy M. Chan. More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3sum-hard problems. In Proceedings of SODA 2018, 2018. to appear. Google Scholar
  7. Erik D. Demaine, John Iacono, and Stefan Langerman. Retroactive data structures. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 274-283, 2004. Google Scholar
  8. Erik D. Demaine, John Iacono, and Stefan Langerman. Retroactive data structures. ACM Transactions on Algorithms, 3(2):13:1-13:21, 2007. Google Scholar
  9. Erik D. Demaine, Tim Kaler, Quanquan Liu, Aaron Sidford, and Adam Yedidia. Polylogarithmic fully retroactive priority queues via hierarchical checkpointing. In Proceedings of the 14th International Symposium on Workshop on Algorithms and Data Structures, pages 263-275. Springer, 2015. Google Scholar
  10. Matthew T. Dickerson, David Eppstein, and Michael T. Goodrich. Cloning voronoi diagrams via retroactive data structures. In Proceedings of the 18th Annual European Symposium on Algorithms, pages 362-373, 2010. Google Scholar
  11. 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
  12. Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971, pages 129-131, 1971. Google Scholar
  13. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry: Theory and Applications, 5:165-185, 1995. Google Scholar
  14. Igal Galperin and Ronald L. Rivest. Scapegoat trees. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 165-174. Society for Industrial and Applied Mathematics, 1993. Google Scholar
  15. Yoav Giora and Haim Kaplan. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Trans. Algorithms, 5(3):28:1-28:51, 2009. Google Scholar
  16. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 421-436, Cham, 2017. Springer International Publishing. Google Scholar
  17. Michael T. Goodrich and Joseph A. Simons. Fully retroactive approximate range and nearest neighbor searching. In Proceedings of the 22nd International Symposium on Algorithms and Computation, pages 292-301, 2011. Google Scholar
  18. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 621-630, 2014. Google Scholar
  19. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 21-30, 2015. Google Scholar
  20. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638, 2017. Google Scholar
  21. 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
  22. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1272-1287, 2016. Google Scholar
  23. Yakov Nekrich. Searching in dynamic catalogs on a tree. CoRR, abs/1007.3415, 2010. URL: http://arxiv.org/abs/1007.3415.
  24. Salman Parsa. Algorithms for the Reeb Graph and Related Concepts. PhD thesis, Duke University, 2014. Google Scholar
  25. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610, 2010. Google Scholar
  26. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. To appear. Google Scholar
  27. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 645-654, Washington, DC, USA, 2010. IEEE Computer Society. 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