In this work, we prove a $\tilde{\Omega}(\lg^{3/2} n )$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.
翻译：-
翻译后的标题：动态图问题的超对数下界
翻译后的摘要：在这项工作中，我们证明了一个$\tilde{\Omega}(\lg^{3/2} n )$的无条件下界，用于支持在插入边时在$n$节点**有向无环图**上的可达性查询的动态数据结构的查询时间和更新时间的最大值。这是对于任何自然的图问题的第一个超对数下界。在证明下界的过程中，我们还对现有技术水平的数据结构下界技术做出了新的贡献，我们希望这些贡献可以促进下界的进一步进展。
相关内容
微信扫码咨询专知VIP会员