论文标题
动态算法的粗粒复杂性
Coarse-Grained Complexity for Dynamic Algorithms
论文作者
论文摘要
迄今为止，争论动态算法的多项式下限的唯一方法是通过细粒的复杂性参数。这些论点依赖于对特定问题的强烈假设，例如强烈的指数时间假设（SETH）和在线矩阵 - 矢量乘法猜想（OMV）。尽管它们导致了许多令人兴奋的发现，但动态算法仍然错过了传统的``粗粒''方法的一些好处和经验教训，这些方法将诸如P和NP等问题类别相关联。在本文中，我们启动了针对动态算法的粗粒复杂性理论的研究。以下是该理论可以回答的问题。 如果动态正交矢量（OV）在细胞探针模型中很容易怎么办？一个用于在细胞探针模型中证明多项式无条件下限的研究计划是由于可以通过减少动态OV问题来显示许多条件下限的事实。由于细胞探针模型比单词RAM更强大，并且在历史上允许较小的上限，因此可能证明动态OV在细胞探针模型中很容易，因此该研究方向是不可行的。 Our theory implies that if this is the case, there will be very interesting algorithmic consequences: If dynamic OV can be maintained in polylogarithmic worst-case update time in the cell-probe model, then so are several important dynamic problems such as $k$-edge connectivity, $(1+ε)$-approximate mincut, $(1+ε)$-approximate matching, planar nearest neighbors, Chan's subset union and 3-VS-4直径。当我们将动态OV替换为例如子图连接，单源可及性，Chan的子集合和3 VS-4直径时，可以得出相同的结论。 $ k $ - 边缘连接的下限通过动态OV？ （请参阅PDF文件中的完整摘要）。
To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific problems such as the Strong Exponential Time Hypothesis (SETH) and the Online Matrix-Vector Multiplication Conjecture (OMv). While they have led to many exciting discoveries, dynamic algorithms still miss out some benefits and lessons from the traditional ``coarse-grained'' approach that relates together classes of problems such as P and NP. In this paper we initiate the study of coarse-grained complexity theory for dynamic algorithms. Below are among questions that this theory can answer. What if dynamic Orthogonal Vector (OV) is easy in the cell-probe model? A research program for proving polynomial unconditional lower bounds for dynamic OV in the cell-probe model is motivated by the fact that many conditional lower bounds can be shown via reductions from the dynamic OV problem. Since the cell-probe model is more powerful than word RAM and has historically allowed smaller upper bounds, it might turn out that dynamic OV is easy in the cell-probe model, making this research direction infeasible. Our theory implies that if this is the case, there will be very interesting algorithmic consequences: If dynamic OV can be maintained in polylogarithmic worst-case update time in the cell-probe model, then so are several important dynamic problems such as $k$-edge connectivity, $(1+ε)$-approximate mincut, $(1+ε)$-approximate matching, planar nearest neighbors, Chan's subset union and 3-vs-4 diameter. The same conclusion can be made when we replace dynamic OV by, e.g., subgraph connectivity, single source reachability, Chan's subset union, and 3-vs-4 diameter. Lower bounds for $k$-edge connectivity via dynamic OV? (see the full abstract in the pdf file).
