Viðburðir eftir árum

Virtual ICE-TCS/GSSI seminar: Magnús M. Halldórsson

Symmetry breaking with your hands tied

  • 20.4.2020, 13:30 - 14:30

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 ( and the seminar will allow us to celebrate this accolade.  Link to join the seminar will be sent on Monday morning. Please contact if you want to get the link.


Title: Symmetry breaking with your hands tied

Magnus M. Halldorsson (ICE-TCS, Department of Computer Science, Reykjavik University)

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.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: