BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260916T045206Z
UID:Seminar-NESTiD-1158@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20221208T161500
DTEND:20221208T171500
SUMMARY:Durham-Liverpool synergy Series
DESCRIPTION:Magnus Halldorsson: Distributed graph coloring: The loglog-revolution\n\nThe graph coloring problem is fundamental to distributed computing, as an elegant way of breaking symmetry and sharing resources. For the core problem of using $\Delta+1$ colors, where $\Delta$ is the maximum degree, a randomized algorithm of Chang, Li and Pettie [STOC’18] achieves the best complexity known of $O(\log^3 \log n)$ rounds of the LOCAL model, when combined with the recent deterministic algorithm of Ghaffari and Kuhn [FOCS’21].\n\nWe describe recent results that are simpler, faster, more general, use fewer colors, and/or are bandwidth efficient. In particular, we give a simplified framework that holds in the CONGEST model and is ultrafast when $\Delta$ is sufficiently large. We apply it to get fast algorithms for the more general degree+1-list coloring and the $\Delta$-coloring problems.\n\nThis is joint work with Manuela Fischer, Fabian Kuhn, Yannic Maus, Alexandre Nolin, and Tigran Tonoyan, appearing in STOC’21, STOC’22, SIROCCO’22, and SODA’23.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1158
LOCATION:
END:VEVENT
END:VCALENDAR