Log Diameter Rounds Algorithms for 2Vertex and 2Edge Connectivity. Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarsegrained computation on large data  data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model.  :103,this paper, we study two fundamental problems, 2edge connectivity and 2vertex connectivity (biconnectivity). PRAM algorithms which run in O(log n) time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an nvertex, medge graph of diameter D and bidiameter Du0027, 1) a O(log Dloglog_mn n) parallel time 2edge connectivity algorithm, 2) a O(log Dlog2log_mnnlog Du0027loglog_mnn) parallel time biconnectivity algorithm, where the bidiameter Du0027 is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be O(ndelta) for arbitrary constant deltau003e0, and the total memory used is linear in the problem size. Our 2edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of Andoni et al. (FOCS 2018). We also show an Omega(log Du0027) conditional lower bound for the biconnectivity problem.

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even local (i.e., with widetildeO(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diamsqrtn) rounds).  :52,main results are:  :56,For Ddiameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in poly(D) rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOCu002719.  :56,For Ddiameter unweighted :94,graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in poly(D)cdot 2O(sqrtlog nloglog n) rounds.  :119,Computation of sparse lambda connectivity certificates in widetildeO(lambda) rounds. Previous constructions where known only for lambda leq 3 and required O(D) rounds. This resolves the problem raised by Dori PODCu002718.