Overcoming Congestion in Distributed Coloring

Summary

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree +1)-list-coloring (D1LC), this allows us to solve D1LC in O(log5 logn) Congest rounds, and in only O(log* n) rounds when the graph has minimum degree Ω(log7 n), w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in O(1) Congest rounds, w.h.p.