Magnús M. Halldórsson

Professor, Department of Computer Science, Reykjavik University

I work on algorithms — distributed graph colouring, approximation algorithms, and more recently dynamic algorithms. I am a Fellow of the EATCS.

Research

My work centres on symmetry breaking in distributed computing — how a network of processors, each seeing only its own neighbourhood, can agree on a colouring or an independent set — and on approximation algorithms for problems where exact answers are out of reach.

• Distributed graph colouring, particularly in the CONGEST model
• Approximation algorithms and their limits
• Scheduling and capacity in wireless networks
• Dynamic graph algorithms

Selected recent papers

• A Distributed Palette Sparsification TheoremSODA 2024
  with Maxime Flin, Mohsen Ghaffari, Fabian Kuhn, Alexandre Nolin
• Fast Coloring Despite Congested RelaysDISC 2023
  with Maxime Flin, Alexandre Nolin
• Coloring Fast with BroadcastsSPAA 2023
  with Maxime Flin, Mohsen Ghaffari, Fabian Kuhn, Alexandre Nolin
• Fast Distributed Brooks' TheoremSODA 2023
  with Manuela Fischer, Yannic Maus

Full list on the publications page, and on DBLP.

Teaching

Hugsun og færni í tölvunarfræði — Becoming a Computer Scientist.

Service

• Chair, Curriculum Council, Reykjavik University
• Fellow of the EATCS
• Steering Committee Chair, SWAT, 2004–2023
• Program Chair, PODC 2023

Contact

Department of Computer Science, Reykjavik University
Menntavegur 1, 102 Reykjavík, Iceland

DBLP · GitHub · ORCID