Brief announcement: Massively parallel ruling set made deterministic

DOI10.1145/3662158.3662816MaRDI QIDQ6971905zbMATH OpenFDO

Authors Jeff Giliberti, Zahra Parsaeian

Publication date 13 June 2025

Full work available at URL https://doi.org/10.1145/3662158.3662816

zbMATH Keywords

derandomizationdeterministic algorithmsdistributed computinggraph algorithmsmassively parallel computation

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites work

• A deterministic algorithm for the MST problem in constant rounds of congested clique
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• An Improved Distributed Algorithm for Maximal Independent Set
• Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets
• Component Stability in Low-Space Massively Parallel Computation
• Conditional hardness results for massively parallel computation from distributed lower bounds
• Derandomizing local distributed algorithms under bandwidth restrictions
• Deterministic massively parallel connectivity
• Distributed ∆-coloring plays hide-and-seek
• Distributed graph coloring in a few rounds
• Distributed Lower Bounds for Ruling Sets
• Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Improved Deterministic (Δ+1) Coloring in Low-Space MPC
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Local computation: lower and upper bounds
• Lower bounds for maximal matchings and maximal independent sets
• Removing randomness in parallel computation without a processor penalty
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Simple, Deterministic, Constant-Round Coloring in the Congested Clique
• Sorting, searching, and simulation in the MapReduce framework
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• The locality of distributed symmetry breaking
• The probabilistic method yields deterministic parallel algorithms

This page was built for publication: Brief announcement: Massively parallel ruling set made deterministic

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