Sample-and-gather: fast ruling set algorithms in the low-memory MPC model

DOI10.4230/LIPICS.FSTTCS.2020.28MaRDI QIDQ6839878zbMATH OpenFDO

Authors Kishore Kothapalli, Shreyas Pai, Sriram Pemmaraju

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.28

zbMATH Keywords

massively parallel computationruling setsimulation theorems

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An Improved Distributed Algorithm for Maximal Independent Set
• Conditional hardness results for massively parallel computation from distributed lower bounds
• Congested clique algorithms for graph spanners
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MIS via all-to-all communication
• Exponentially faster massively parallel maximal matching
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Round compression for parallel matching algorithms
• Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Sublinear algorithms for ( + 1) vertex coloring
• Super-fast 3-ruling sets
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• The locality of distributed symmetry breaking
• What cannot be computed locally!

Cited in

(2)

• Massively parallel computation in a heterogeneous regime
• Brief announcement: Massively parallel ruling set made deterministic

This page was built for publication: Sample-and-gather: fast ruling set algorithms in the low-memory MPC model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6839878)