Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
复制标题
简短公告：一种随机高效的大规模并行连接算法
DOI：
10.1145/3465084.3467951
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tan, Li-Yang
中科院分区：
文献类型：
--
作者：
Charikar, Moses;Ma, Weiyun;Tan, Li-Yang
给出了一个判定无向图是否连通的随机性高效的大规模并行计算(MPC)算法。对于连通度最大为D=20(logn/logn)的n点m边图，我们的算法运行在R=O(logD+loglogm/n，.N)轮，每台机器总共使用(Logn)O(R)个随机比特，O(M)台机器，以及N1-Ω(1)空间，1具有良好的概率均值，概率至少为1-1/Poly(Mlogn)/n，这与Liu，Tarjan和钟(SPAA‘20)中的相同。与Andoni等人的突破性算法相比，我们的算法在随机性复杂度上实现了超多项式的节省。(Focs‘18)和Behnezhad等人随后的改进。(Focs‘19)我们的算法具有与Behnezhad等人相同的轮次复杂度，但使用了更多的总空间。我们的连通性算法是我们开发的将PRAM模型中的随机化算法转换为高度随机性高效的MPC算法的通用方法的实例化。证明了当k=o(logn/loglogn)且p=no(1)时，任何在n个输入比特上计算函数的时间为k的p处理机随机PRAM算法都可以转化为一个具有O(K)轮且总共只有(Logn)O(K)个随机比特的强次线性MPC算法。我们的连通性算法是将这种方法应用于最近的CRCW PRAM算法(SPAA‘20)。我们的方法基于PRAM算法的伪随机产生器的设计。我们对生成器的分析建立在电路复杂性方面的经典和有影响力的结果(哈斯塔德‘86；Nisan和Wigderson’88)的基础上，我们将其从小深度电路的设置推广到更强大的PRAM算法设置。在复杂性理论的当前技术状态下，我们实现的参数是最优的，从某种意义上说，进一步的改进将意味着≠Nc1。
We give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our algorithm runs in R = O(log D + log logm/n,.n) rounds and uses a total of (log n)O(R) random bits, O(m) machines, and n1-Ω(1) space per machine with good probability.1 With good probability means with probability at least 1 - 1/poly ((m log n)/n), which is the same as in Liu, Tarjan, and Zhong (SPAA '20). Our algorithm achieves a super-polynomial saving in randomness complexity as compared to the breakthrough algorithm of Andoni et al. (FOCS '18) and the subsequent improvement by Behnezhad et al. (FOCS '19). Our algorithm has the same round complexity as that of Behnezhad et al., but uses more total space.Our Connectivity algorithm is an instantiation of a general method we develop for converting randomized algorithms in the PRAM model to highly randomness-efficient MPC algorithms. We show that for k = o(log n/log log n) and p = nO(1), any time-k p-processor randomized PRAM algorithm computing a function on n input bits can be converted to an equivalent strongly sublinear MPC algorithm with O(k) rounds and only a total of (log n)O(k) random bits. Our Connectivity algorithm follows from applying this method to the recent CRCW PRAM algorithm of Liu, Tarjan, and Zhong (SPAA '20).Our approach is based on the design of a pseudorandom generator for PRAM algorithms. The analysis of our generator is built on classic and influential results in circuit complexity (Hå stad '86; Nisan and Wigderson '88), which we generalize from the setting of small-depth circuits to the more powerful setting of PRAM algorithms. The parameters that we achieve are optimal given the current state of the art in complexity theory, in the sense that further improvements will imply ≠ NC1.
登录
查看更多内容
PRAM 上的连接组件（以日志直径时间表示）
DOI：
10.1145/3350755.3400249
发表时间：
2020
期刊：
32nd ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Liu, Sixue Cliff;Tarjan, Robert E.;Zhong, Peilin
通讯作者：
Zhong, Peilin
关于深度有限的单调公式
DOI：
--
发表时间：
1984
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
M. Klawe;W. Paul;N. Pippenger;M. Yannakakis
通讯作者：
M. Yannakakis
去随机化的切换引理和改进的 AC0 去随机化
DOI：
--
发表时间：
2013
期刊：
2013 IEEE Conference on Computational Complexity
影响因子：
--
作者：
L. Trevisan;Tongke Xue
通讯作者：
Tongke Xue
DOI：
--
发表时间：
2019
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
P. Bamberger;F. Kuhn;Yannic Maus
通讯作者：
Yannic Maus
多项式的去随机浓度界限和超图最大独立集
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
David G. Harris
通讯作者：
David G. Harris