论文标题
紧密的动态问题从广义BMM和OMV降低了界限
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
论文作者
论文摘要
本文的主要主题是使用$ k $维的概括（组合布尔矩阵乘法（BMM）假设和密切相关的在线矩阵矢量乘法（OMV）假设，证明动态问题的新紧密有条件下限。 组合$ k $ clique假设是文献中的标准假设，自然会概括组合BMM假设。在本文中，在组合$ k $ clique假设下，我们证明了几个动态问题的紧密下限。例如，我们表明： *动态范围模式问题没有组合算法，$ \ mathrm {poly}（n）$预处理时间，$ o（n^{2/3-ε}）$更新时间和$ o（n^{2/3-ε}）$（n^{2/3-ε}）$查询时间，符合已知上限的任何$ε> 0 $。以前的下限仅以$ o（n^{1/2-ε}）$更新和查询时间在OMV假设下排除了算法。 其他示例包括用于动态子图连接性的紧密组合下限，动态2D正交范围颜色计数，动态的2件模式文档检索和动态范围模式在更高的维度中。 此外，我们将OUMV $ _K $假设作为OMV假设的自然概括。在这一假设下，我们证明了各种动态问题的紧密下限。例如，我们表明： * $（2K-1）$ - 尺寸空间中的动态天际线计数问题没有算法，$ \ mathrm {poly}（n）$预处理时间和$ o（n^{1-1/k-ε}）$更新和查询时间$ε> 0 $，即使更新是半键的$ε> 0 $。 其他示例包括（半结）动态KLEE对单位立方体的度量的紧密条件下限，以及Erickson问题和Langerman的问题的高维概括。
The main theme of this paper is using $k$-dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis to prove new tight conditional lower bounds for dynamic problems. The combinatorial $k$-Clique hypothesis, which is a standard hypothesis in the literature, naturally generalizes the combinatorial BMM hypothesis. In this paper, we prove tight lower bounds for several dynamic problems under the combinatorial $k$-Clique hypothesis. For instance, we show that: * The Dynamic Range Mode problem has no combinatorial algorithms with $\mathrm{poly}(n)$ pre-processing time, $O(n^{2/3-ε})$ update time and $O(n^{2/3-ε})$ query time for any $ε> 0$, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with $O(n^{1/2-ε})$ update and query time under the OMv hypothesis. Other examples include tight combinatorial lower bounds for Dynamic Subgraph Connectivity, Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-Pattern Document Retrieval, and Dynamic Range Mode in higher dimensions. Furthermore, we propose the OuMv$_k$ hypothesis as a natural generalization of the OMv hypothesis. Under this hypothesis, we prove tight lower bounds for various dynamic problems. For instance, we show that: * The Dynamic Skyline Points Counting problem in $(2k-1)$-dimensional space has no algorithm with $\mathrm{poly}(n)$ pre-processing time and $O(n^{1-1/k-ε})$ update and query time for $ε> 0$, even if the updates are semi-online. Other examples include tight conditional lower bounds for (semi-online) Dynamic Klee's measure for unit cubes, and high-dimensional generalizations of Erickson's problem and Langerman's problem.
