Equivalence classes and conditional hardness in massively parallel computations.
Equivalence classes and conditional hardness in massively parallel computations.
复制标题
DOI：
10.1007/s00446-021-00418-2
复制
发表时间：
2022
影响因子：
1.3
通讯作者：
Scquizzato M
中科院分区：
文献类型：
--
作者：
Nanongkai D;Scquizzato M
下限条件的一个循环与两个循环猜想可以在猜想下进行论证：这两个假设是等价的，并且反驳其中任何一个都会导致多轮MPC算法用于大量具有挑战性的问题，包括列表排名，最小切割和平面性测试。事实上，我们表明，这些问题和许多其他问题需要渐近相同的轮数，似乎更容易区分一个图是一个周期或两个周期的问题。许多以前在一个循环对两个循环猜想下争论的下界可以在一个更强大（因此更难反驳）的猜想下争论，即。反驳这一猜想将导致多轮MPC算法的问题，甚至更大的集合，包括所有对最短路径，介数中心，和所有上述的。这个猜想下的下界适用于完美匹配和网络流等问题。大规模并行计算（MPC）模型作为许多现代大规模数据处理框架的通用抽象，在过去几年中受到越来越多的关注，特别是在经典图问题的背景下。到目前为止，讨论这个模型的下界的唯一方法是以一些特定问题的难度为条件，例如承诺图上的图连通性是一个周期还是两个周期，通常称为一个周期与两个周期问题。这与传统的基于复杂性类的假设的论点不同（例如，），它们通常更健壮，因为反驳它们会导致一大堆问题的突破性算法。在本文中，我们提出的问题和类的问题，允许后一种类型的参数之间的连接。这些连接涉及的类问题可解决的次对数数量的回合在MPC模型中，表示为，和标准的空间复杂性类和，并建议在这个意义上，反驳他们将导致许多令人惊讶的快速的新算法在MPC模型中的鲁棒性。我们还获得了新的条件下界，并证明了新的减少和MPC模型中的问题之间的等价性。具体而言，我们的主要结果如下。
Lower bounds conditioned on the one cycle versus two cycles conjecture can be instead argued under the conjecture: these two assumptions are equivalent, and refuting either of them would lead to -round MPC algorithms for a large number of challenging problems, including list ranking, minimum cut, and planarity testing. In fact, we show that these problems and many others require asymptotically the same number of rounds as the seemingly much easier problem of distinguishing between a graph being one cycle or two cycles. Many lower bounds previously argued under the one cycle versus two cycles conjecture can be argued under an even more robust (thus harder to refute) conjecture, namely . Refuting this conjecture would lead to -round MPC algorithms for an even larger set of problems, including all-pairs shortest paths, betweenness centrality, and all aforementioned ones. Lower bounds under this conjecture hold for problems such as perfect matching and network flow. The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle versus two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., ), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by , and the standard space complexity classes and , and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model. Specifically, our main results are as follows.
登录
查看更多内容
影响因子：
1.4
作者：
Alvarez, C;Greenlaw, R
通讯作者：
Greenlaw, R
影响因子：
2.5
作者：
Behnezhad, Soheil;Dhulipala, Laxman;Schudy, Warren
通讯作者：
Schudy, Warren
影响因子：
1.1
作者：
BEAUDRY, M;MCKENZIE, P
通讯作者：
MCKENZIE, P
影响因子：
1.6
作者：
Bilardi, Gianfranco;Scquizzato, Michele;Silvestri, Francesco
通讯作者：
Silvestri, Francesco
影响因子：
1
作者：
Allender, E;Mahajan, M
通讯作者：
Mahajan, M