Massively Parallel Ruling Set Made Deterministic
<|reference_start|>Massively Parallel Ruling Set Made Deterministic: We study the deterministic complexity of the $2$-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory.   Linear MPC: We present a constant-round deterministic algorithm for the $2$-Ruling Set problem that matches the randomized round complexity recently settled by Cambus, Kuhn, Pai, and Uitto [DISC'23], and improves upon the deterministic $O(\log \log n)$-round algorithm by Pai and Pemmaraju [PODC'22]. Our main ingredient is a simpler analysis of CKPU's algorithm based solely on bounded independence, which makes its efficient derandomization possible.   Sublinear MPC: We present a deterministic algorithm that computes a $2$-Ruling Set in $\tilde O(\sqrt{\log n})$ rounds deterministically. Notably, this is the first deterministic ruling set algorithm with sublogarithmic round complexity, improving on the $O(\log \Delta + \log \log^* n)$-round complexity that stems from the deterministic MIS algorithm of Czumaj, Davies, and Parter [TALG'21]. Our result is based on a simple and fast randomness-efficient construction that achieves the same sparsification as that of the randomized $\tilde O(\sqrt{\log n})$-round LOCAL algorithm by Kothapalli and Pemmaraju [FSTTCS'12].<|reference_end|>
@article{giliberti2024massively,
    title={Massively Parallel Ruling Set Made Deterministic},
    author={Jeff Giliberti, Zahra Parsaeian},
    journal={arXiv preprint arXiv:2406.12727},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.12727},
    primaryClass={cs.DS cs.DC}
}