2018/07/17 by Mohsen Ghaffari, Ghaffari, Mohsen, Jara Uitto +1 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1807.06251
openalex publication_date 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). - MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic O(log n)-round parallel counterparts for problems such as MIS, Maximal Matching, 2-Approximation of Minimum Vertex Cover, and (1+ε)-Approximation of Maximum Matching. Currently, all such MPC algorithms require Ω(n) memory per machine. Czumaj et al. [STOC'18] were the first to handle Ω(n) memory, running in O((loglog n)2) rounds. We obtain O(√(log Δ))-round MPC algorithms for all these four problems that work even when each machine has memory nα for any constant α∈ (0, 1). Here, Δ denotes the maximum degree. These are the first sublogarithmic-time algorithms for these problems that break the linear memory barrier. - LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity ΔO(log Δ) poly(log n), by Ghaffari [SODA'16]. As pointed out by Rubinfeld, obtaining a query complexity of poly(Δlog n) remains a central open question. Ghaffari's bound almost reaches a ΔΩ((log Δ)/(loglog Δ)) barrier common to all known MIS LCAs, which simulate distributed algorithms by learning the local topology, à la Parnas-Ron [TCS'07]. This barrier follows from the Ω((log Δ)/(loglog Δ)) distributed lower bound of Kuhn, et al. [JACM'16]. We break this barrier and obtain an MIS LCA with query complexity ΔO(loglog Δ) poly(log n).