Cell-probe lower bounds from online communication complexity
Cell-probe lower bounds from online communication complexity
复制标题
在线通信复杂性的细胞探针下限
DOI：
10.1145/3188745.3188862
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yu, Huacheng
中科院分区：
文献类型：
--
作者：
Alman, Josh;Wang, Joshua R.;Yu, Huacheng
在这项工作中，我们引入了通信复杂性的在线模型。与在线算法如何逐个接收输入类似，我们的模型会逐个呈现玩家之一鲍勃的输入，并让玩家爱丽丝和鲍勃每次合作计算结果，然后再将下一个片段透露给鲍勃。该模型比经典通信模型与动态数据结构具有更紧密、更自然的对应关系，因此提出了数据结构的新视角。我们首先提出了在线通信模型中在线集合交集问题的严格下界，展示了证明在线通信下界的通用方法。在线通信模型可以防止经典通信复杂性所允许的批处理技巧，并产生更强的下限。然后，我们应用在线通信模型来证明两个动态数据结构问题的数据结构下界：组范围问题和森林的动态连接问题。这两个问题都承认最坏情况的 O(logn) 时间数据结构。使用在线通信复杂性，我们证明了每个操作的严格单元探测下界：每次操作花费 o(logn)（甚至摊销）时间最多导致正确回答查询的 (1/2+δ) 部分的 exp(−δ2n) 概率。
In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures.We first present a tight lower bound for theonline set intersectionproblem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst caseO(logn)-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spendingo(logn) (even amortized) time per operation results in at best an exp(−δ2n) probability of correctly answering a (1/2+δ)-fraction of thenqueries.
登录
查看更多内容
DOI：
10.1109/focs.2015.71
发表时间：
2015-04
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
R. Clifford;A. Jørgensen;Kasper Green Larsen
通讯作者：
R. Clifford;A. Jørgensen;Kasper Green Larsen
通过新的通信模型来探测动态问题的细胞探测下限
DOI：
10.1145/2897518.2897556
发表时间：
2015
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Huacheng Yu
通讯作者：
Huacheng Yu
DOI：
10.1145/320211.320215
发表时间：
1999-07
期刊：
J. ACM
影响因子：
--
作者：
Monika Henzinger;Valerie King
通讯作者：
Monika Henzinger;Valerie King
DOI：
10.1145/335305.335345
发表时间：
2000-05
期刊：
--
影响因子：
--
作者：
M. Thorup
通讯作者：
M. Thorup
动态应用题
DOI：
10.1109/sfcs.1993.366840
发表时间：
1993
期刊：
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
影响因子：
--
作者：
G. Frandsen;Peter Bro Miltersen;Sven Skyum
通讯作者：
Sven Skyum