An Optimal Distributed (Delta+1)-Coloring Algorithm?

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized sf LOCAL model running in O(mathsfDetscriptscriptstyle d(poly log n)) time, where mathsfDetscriptscriptstyle d(n') is the deterministic complexity of (deg+1)-list coloring on n'-vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [STOC'16, JACM'18] with complexity O(√log Delta + loglog n + mathsfDetscriptscriptstyle d(poly log n)), and, for some range of Delta, is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [FOCS'16] and Barenboim, Elkin, and Goldenberg [PODC'18], with complexity O(√Deltalog Deltalog^ast Delta + log^* n). Our algorithm "appears to be" optimal, in view of the Omega(mathsfDet(poly log n)) randomized lower bound due to Chang, Kopelowitz, and Pettie [FOCS'16], where mathsfDet is the deterministic complexity of (Delta+1)-list coloring. At present, the best upper bounds on mathsfDetscriptscriptstyle d(n') and mathsfDet(n') are both 2^O(√log n') and use a black box application of network decompositions (Panconesi and Srinivasan [Journal of Algorithms'96]). It is quite possible that the true complexities of both problems are the same, asymptotically, which would imply the randomized optimality of our (Delta+1)-list coloring algorithm.