Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model

Kishore Kothapalli, Shreyas Pai, Sriram V. Pemmaraju

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (…