...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures
【24h】

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures

机译：部分追溯数据结构和完全追溯数据结构之间的最佳分离

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：自从SODA 2004引入追溯数据结构以来，一个主要的悬而未决的问题是限制最好的部分追溯数据结构（可以对过去进行更改，但只能查询当前）和最好的完全追溯数据结构之间的差距。追溯数据结构（也可以查询过去）。 2004年证明，任何具有操作时间T_ {op}（n，m）的部分追溯数据结构都可以转换为具有操作时间O（sqrt {m} * T_ {op}（n，m）的完全追溯数据结构）），其中n是数据结构的大小，m是时间轴中的操作数[Demaine et al。，2004]。但是是否需要这样的间隔已经开放了14年。在本文中，我们证明了对于所有n和m，该间隔的上下限几乎匹配。通过显示具有乘法开销n log m的新变换，我们提高了n sqrt m的上限。然后，我们假设以下任意一个猜想，证明了min {n log m，sqrt m} ^ {1-o（1）}的下界：-猜想I：电路SAT需要2 ^ {n-o（n）}时间在大小为2 ^ {o（n）}的n个输入电路上。该猜想远比复杂度理论中公认的SETH猜想要弱得多，复杂度理论认为带有n个变量和O（n）子句的CNF SAT已经需要2 ^ {no（n）}时间。-猜想II：在线（最小， +）整数nxn矩阵与n个向量的乘积需要n ^ {3-o（1）}时间。此猜想比在细粒度复杂度中广泛使用的APSP猜想要弱。-猜想III（3-SUM猜想）：给定三组A，B，C整数，每个大小为n，确定A中是否存在a， B中的b，C中的c，使得a + b + c = 0需要n ^ {2-o（1）}时间。这个1995年的猜想[Anka Gajentaan和Mark H.Overmars，1995年]是第一个具有细粒度复杂性的猜想。我们的下界构造说明了完全追溯查询的一种有趣功能：它们可用于快速解决批量对评估。我们认为，该技术可证明对其他数据结构下限（尤其是动态边界）有用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号