论文标题
在大规模平行计算中等效类别和有条件硬度
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
论文作者
论文摘要
大规模并行计算（MPC）模型是许多现代大规模数据处理框架的共同抽象，并且在过去几年中，人们一直受到越来越多的关注，尤其是在经典图形问题的背景下。到目前为止，争论该模型的下限的唯一方法是条件对某些特定问题的硬度的猜想进行条件，例如在承诺图上的图形连接性是一个周期或两个周期，通常称为一个周期与两个周期问题。这与基于关于复杂性类别的猜想的传统论点不同（例如，$ \ textsf {p} \ neq \ textsf {np} $）通常更强大，从而导致它们会导致它们为整个问题带来突破性的算法。 在本文中，我们介绍了问题与允许后一种参数类型的问题之间的联系。 These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by $\textsf{MPC}(o(\log N))$, and some standard classes concerning space complexity, namely $\textsf{L}$ and $\textsf{NL}$, and suggest conjectures that are robust in the sense that refuting them would导致MPC模型中许多令人惊讶的快速新算法。我们还获得了新的条件下限，并证明了MPC模型中问题之间的新减少和等价。
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 vs. two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., $\textsf{P} \neq \textsf{NP}$), 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 $\textsf{MPC}(o(\log N))$, and some standard classes concerning space complexity, namely $\textsf{L}$ and $\textsf{NL}$, 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.
