Equivalence Classes and Conditional Hardness in Massively Parallel Computations. The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern largescale 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., textsfP neq textsfNP), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems.  this :124,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 textsfMPC(o(log N)), and some standard classes concerning space complexity, namely textsfL and textsfNL, 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.

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.