Conditional hardness results for massively parallel computation from distributed lower bounds

DOI10.1109/FOCS.2019.00097MaRDI QIDQ6944137zbMATH OpenFDO

Authors Fabian Kuhn, Mohsen Ghaffari, Jara Uitto

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00097

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(7)

• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Fully-scalable MPC algorithms for clustering in high dimension
• Massively parallel computation in a heterogeneous regime
• Brief announcement: Massively parallel ruling set made deterministic
• Parallel derandomization for coloring
• Constant-round spanners and shortest paths in congested clique and MPC

This page was built for publication: Conditional hardness results for massively parallel computation from distributed lower bounds

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