论文标题
从查询复杂性大规模平行计算的新下限
New lower bounds for Massively Parallel Computation from query complexity
论文作者
论文摘要
Roughgarden，Vassilvitskii和Wang（JACM 18）最近引入了一个新颖的框架，用于使用布尔功能复杂性的技术证明大规模平行计算的下限。我们以两种不同的方式扩展了他们的框架，以捕获大规模并行计算的两个共同特征： $ \ circ $自适应性，在整个计算执行过程中，机器可以从共享内存中写入并自适应地读取。 Behnezhad等人的最新工作。 （SPAA 19）表明，适应性可以显着改善许多中心图问题的圆形复杂度。 $ \ circ $承诺问题，其中算法只需要在某些输入上取得成功。这些输入可能具有特别感兴趣的特殊结构，或者它们可能代表了整个问题的硬实例。 使用此扩展框架，我们将第一个无条件的下限给出了区分输入图是长度$ n $还是两个循环长度为$ n/2 $的复杂性的复杂性。在大规模平行计算的研究中，这个有望的问题是1V2周期。我们证明，每台机器的I/O容量$ o（n^{\ varepsilon}）$的1V2周期问题的任何自适应算法都需要$ω（1/\ varepsilon）$ rounds，与Behnezhad等人的最新上限相匹配。 除了加强大规模并行计算与布尔功能复杂性之间的连接外，我们还开发了新的机械来推理后者。我们证明的核心是查询复杂性的最佳下限和1V2周期问题的近似证书复杂性。
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a novel framework for proving lower bounds for Massively Parallel Computation using techniques from boolean function complexity. We extend their framework in two different ways, to capture two common features of Massively Parallel Computation: $\circ$ Adaptivity, where machines can write to and adaptively read from shared memory throughout the execution of the computation. Recent work of Behnezhad et al. (SPAA 19) showed that adaptivity enables significantly improved round complexities for a number of central graph problems. $\circ$ Promise problems, where the algorithm only has to succeed on certain inputs. These inputs may have special structure that is of particular interest, or they may be representative of hard instances of the overall problem. Using this extended framework, we give the first unconditional lower bounds on the complexity of distinguishing whether an input graph is a cycle of length $n$ or two cycles of length $n/2$. This promise problem, 1v2-Cycle, has emerged as a central problem in the study of Massively Parallel Computation. We prove that any adaptive algorithm for the 1v2-Cycle problem with I/O capacity $O(n^{\varepsilon})$ per machine requires $Ω(1/\varepsilon)$ rounds, matching a recent upper bound of Behnezhad et al. In addition to strengthening the connections between Massively Parallel Computation and boolean function complexity, we also develop new machinery to reason about the latter. At the heart of our proofs are optimal lower bounds on the query complexity and approximate certificate complexity of the 1v2-Cycle problem.
