论文标题
大规模平行计算中的确定性连通性提高了
Improved Deterministic Connectivity in Massively Parallel Computation
论文作者
论文摘要
关于连通性在大规模平行的计算模型中的一长串研究已经达到了Andoni等人的开创性作品。 [FOCS'18]和Behnezhad等。 [焦点19]。他们为低空MPC提供了一种随机算法，并猜想是最佳的圆形复杂性$ O（\ log d + \ log \ log \ log _ {\ frac m n} n）$和$ o（m）$ space，用于$ n $ Vertices上的图形，带有$ M $ edges和Diameter $ d $。令人惊讶的是，Coy和Czumaj [Stoc'22]的最新结果显示了如何确定性地实现相同的结果。但是，不幸的是，它们的算法遭受了较大的本地计算时间。我们提出了一种确定性连通性算法，该算法与随机算法的所有参数匹配，此外，将局部计算时间显着减少到几乎是线性。我们的降低方法基于减少允许进行更简单搜索所需的随机性量。尽管以前已经使用过类似的随机性降低方法，但我们的结果不仅更简单，而且是第一个具有有效局部计算的方法。这就是为什么我们认为它可以作为低内存MPC中计算有效降低方法的系统开发的起点的原因。
A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. They provide a randomized algorithm for low-space MPC with conjectured to be optimal round complexity $O(\log D + \log \log_{\frac m n} n)$ and $O(m)$ space, for graphs on $n$ vertices with $m$ edges and diameter $D$. Surprisingly, a recent result of Coy and Czumaj [STOC'22] shows how to achieve the same deterministically. Unfortunately, however, their algorithm suffers from large local computation time. We present a deterministic connectivity algorithm that matches all the parameters of the randomized algorithm and, in addition, significantly reduces the local computation time to nearly linear. Our derandomization method is based on reducing the amount of randomness needed to allow for a simpler efficient search. While similar randomness reduction approaches have been used before, our result is not only strikingly simpler, but it is the first to have efficient local computation. This is why we believe it to serve as a starting point for the systematic development of computation-efficient derandomization approaches in low-memory MPC.
