Virtual ICE-TCS/GSSI seminar: Magnús M. Halldórsson
Symmetry breaking with your hands tied
The second ICE-TCS@Reykjavik University/GSSI virtual seminar will be delivered by Magnus M. Halldorsson (ICE-TCS, Department of Computer Science, Reykjavik University) on Monday, 20 April, at 13:30GMT/15:30 Italian time.
Magnus has been the scientific director of ICE-TCS since 2005 and is a member of the Scientific Committee for the PhD programme in CS at the GSSI. He has recently been named as EATCS Fellow (https://eatcs.org/index.php/eatcs-fellows) and the seminar will allow us to celebrate this accolade. Link to join the seminar will be sent on Monday morning. Please contact luca@ru.is if you want to get the link.
---------------------
Title: Symmetry breaking with your hands tied
Speaker: Magnus M. Halldorsson (ICE-TCS, Department of Computer Science, Reykjavik University) https://www.ru.is/~mmh/
Abstract: A key issue in concurrent or distributed systems is to break symmetry or avoiding resource contention. This is commonly achieved by coloring the underlying graph. We are interested in the fundamental question: How powerful must the distributed model be so that graph coloring can be achieved quickly (say, in logarithmic time in the size of the graph).
We explore this question in the setting of *distance-2 coloring*, where nodes of distance at least 2 must receive different colors. This can be viewed as the ordinary coloring problem in a restricted communication model, where messages must go through capacity constrained intermediaries. This turns out to be quite an interesting problem in a meta-research sense -- one where standard approaches fail, but still it ultimately capitulates and admits surprisingly fast algorithms.
This is based on joint (unpublished) work with Fabian Kuhn and Yannic Maus.
