论文标题
进一步统一细胞探针下限的景观
Further Unifying the Landscape of Cell Probe Lower Bounds
论文作者
论文摘要
在具有里程碑意义的纸中，Pǎtraşcu演示了蝴蝶图中静态数据结构问题的单个下限如何通过减少来得出大量新的和以前的下限。对于许多静态数据结构问题，这些下限很紧。此外，他还表明，蝴蝶图中的可达性还原为动态标记的祖先，这是一个经典问题，用于证明动态数据结构的下限。不幸的是，pǎtraşcu减少了标记的祖先，损失了$ \ lg \ lg n $因子，因此缺乏完全恢复所有先前的动态数据结构从明显的祖先随后的下限。在本文中，我们重新审视了pǎtraşcu的作品，并为动态标记的祖先提供了新的无损减少，从而在蝴蝶图中建立了可及性，作为单个种子问题，从中，一系列紧密的静态和动态数据结构从中下降。
In a landmark paper, Pǎtraşcu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Pǎtraşcu's reduction to marked ancestor loses a $\lg \lg n$ factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Pǎtraşcu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow.
