Department of Mathematics FAS Harvard University One Oxford Street Cambridge MA 02138 USA Tel: (617) 495-2171 Fax: (617) 495-5132

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]
Privacy Digital Accessibility