Noah Golowich, Distributed Graph Coloring, April 30, 2019
|
Speaker: Noah Golowich, April 30, 2019 Title. Distributed Graph Coloring Abstract. In the problem of distributed graph coloring, processors located at the vertices of a graph communicate by passing messages over the edges of this graph in multiple rounds according to a pre-determined protocol. The goal of such a protocol is for the processors to compute a proper coloring of the graph, using only the local information collected from the messages. Many exciting advances pertaining to this question have been made in the last few years, yet some fundamental questions remain open. I will discuss some algorithms and lower bounds for special cases of the distributed graph coloring problem, as well as connections with topological methods for lower-bounding the chromatic number of a graph. |
Poster [PDF]