Title: Parallel Derandomization for Coloring

Abstract: 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 \emph{deterministic} algorithms for these problems has been found particularly challenging.
In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the \emph{Massively Parallel Computation} (MPC) model with sublinear space. We give an application of this framework by showing that a recent $(degree+1)$-list coloring algorithm by Halldorsson et al. (STOC'22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in $O(\log \log \log n)$ rounds, which matches the complexity of the state of the art algorithm for the $(\Delta + 1)$-coloring problem.