Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta

The problem of coloring the edges of an $n$-node graph of maximum degree $Delta$ with $2Delta - 1$ colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on $Delta$ has been a long-standing open question. Very recently, Kuhn [SODA 20] showed that the problem can be solved in time $2^{O(sqrt{logDelta})}+O(log^* n)$. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the $(mathit{degree}+1)$-list edge coloring problem, and thus also the $(2Delta-1)$-edge coloring problem, can be solved deterministically in time $log^{O(loglogDelta)}Delta + O(log^* n)$. This is a significant improvement over the result of Kuhn [SODA 20].