Outputs (2)

Parallel Derandomization for Coloring (2024)
Presentation / Conference Contribution
Coy, S., Czumaj, A., Davies-Peck, P., & Mishra, G. (2024, May). Parallel Derandomization for Coloring. Presented at 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2024), San Francisco

Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found... Read More about Parallel Derandomization for Coloring.

Component stability in low-space massively parallel computation (2024)
Journal Article
Czumaj, A., Davies-Peck, P., & Parter, M. (2024). Component stability in low-space massively parallel computation. Distributed Computing, 37(1), 35-64. https://doi.org/10.1007/s00446-024-00461-9

In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algo... Read More about Component stability in low-space massively parallel computation.