Magnús M. Halldórsson

Professor, Department of Computer Science, Reykjavik University

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

Research

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

Selected recent papers

Full list on the publications page; also on DBLP and Google Scholar.

Notes

A note on independent set approximation (PDF)

Polynomial-time consequences of recent results of Lovett and Song, with density-dependent bounds and historical context.

Group

Past members on a separate page.

Current Teaching

Hugsun og færni í tölvunarfræði — Becoming a Computer Scientist.
First-year course, autumn 2026, with Hildur Davíðsdóttir.

Gervigreind og samfélagið (AI and Society).
Spring 2027, with Anna Sigríður Islind.

Gervigreindarsmiðja (Agentic AI Studio).
Spring 2027, with Stefán Ólafsson.

Service (selected)

Contact

Email: magnusmh at gmail

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

DBLP · Google Scholar · ORCID · GitHub · Vita (PDF)