论文标题
通过损坏的半自适应数据结构的下限
Lower Bounds for Semi-adaptive Data Structures via Corruption
论文作者
论文摘要
在动态数据结构问题中，我们希望以一种方式维护某些数据的编码，以便我们可以有效地执行一系列查询和对数据的更新。该领域的一个长期开放问题是证明更新时间和自适应动态数据结构的查询时间之间的无条件多项式下限，计算某些明确的功能。 KO和Weinstein为{\ em半自动\}数据结构提供了如此的下限，以计算脱节功能。 There, the data are subsets $x_1,\dots,x_k$ and $y$ of $\{1,\dots,n\}$, the updates can modify $y$ (by inserting and removing elements), and the queries are an index $i \in \{1,\dots,k\}$ (query $i$ should answer whether $x_i$ and $y$ are脱节，即，它应该计算应用于$（x_i，y）$）的脱节功能。半适应性对如何访问数据结构以回答查询有限制。我们将KO和Weinstein的下限概括为不仅是为了脱节，而且是为了在光滑的腐败束缚下具有很高复杂性的任何功能。
In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the data. A long-standing open problem in this area is to prove an unconditional polynomial lower bound of a trade-off between the update time and the query time of an adaptive dynamic data structure computing some explicit function. Ko and Weinstein provided such lower bound for a restricted class of {\em semi-adaptive\} data structures, which compute the Disjointness function. There, the data are subsets $x_1,\dots,x_k$ and $y$ of $\{1,\dots,n\}$, the updates can modify $y$ (by inserting and removing elements), and the queries are an index $i \in \{1,\dots,k\}$ (query $i$ should answer whether $x_i$ and $y$ are disjoint, i.e., it should compute the Disjointness function applied to $(x_i, y)$). The semi-adaptiveness places a restriction in how the data structure can be accessed in order to answer a query. We generalize the lower bound of Ko and Weinstein to work not just for the Disjointness, but for any function having high complexity under the smooth corruption bound.
