Magnus M. Halldorsson

News and Events 2022-2023

• Project funded by the Icelandic Research Fund: Constrained Distributed Symmetry Breaking
• Program chair for PODC 2023
• Paper on fast distributed Brooks' theorem, in SODA'23.
• Recent talks:
• [18 Nov 2022] "Local Brooks' Theorems" at George Mason University combinatorics seminar
• [29 Nov 2022] "When can we color fast?", workshop honoring Pierre Fraigniaud
• [8 Dec 2022] "Distributed graph coloring: The loglog-revolution" at NestID seminar.
• Paper on fast distributed degree+1-coloring algorithms in STOC'22.

2021

• Best paper award at SIROCCO'21
• Paper on fast distributed coloring in CONGEST in STOC'21
• Elected EATCS Fellow

Research

My main research interests are in the design and analysis of algorithms, in particular approximation algorithms for combinatorial NP-hard problems. My current main focus is on distributed algorithms, particularly for graph coloring problems.

In the past, I have had interests in bioinformatics and biological computing, security, and the sociological aspects of a networked world. Until recently, the main focus was on wireless algorithmics, particularly on combining rigorous algorithms analysis with realistic models of interference.

• Most of my papers appear in full on arXiv
• See also (not fully up-to-date) lists of papers on: Wireless Algorithmics and Algorithms and Complexity
• Curriculum vitae
• My pages on Google Scholar, DBLP, and MathSciNet.

Activities (2016 -- 2020)

• Invited plenary talk at DCOSS, Santorini, May 2019.
• Invited talk at Highlights of Algorithms, June 2018, for paper that received best paper award at ICALP 2017.
• WiOpt 2016, Tempe, Arizona
• BCTCS 2016, Belfast, UK

• Organizing seminar at Dagstuhl on Scheduling, March 2018.
• Organizing a seminar at Dagstuhl on Foundations of Wireless Networking, jointly with Christina Fragouli, Kyle Jamieson, and Bhaskar Krishnamachari, july 2017.
• Organizing SWAT 2016 at Reykjavik University, June 22 - 24, 2016.
• Organizing WRAWN (Workshop on Realistic models for Algorithms in Wireless Networks, July 29, 2016, co-located with PODC, Chicago, Illinois.

• SIROCCO (chair)
• ALGOSENSORS
• SWAT, Scandinavian Symposium and Workshops on Algorithm Theory (chair)

Members of Lab

• Maxime Flin, Ph.D. student, April 2022 --

Alumni

• Alexandre Nolin, post-doc, February 2020 -- Oct 2022
• Duncan Adamson, post-doc, Sept 2021 -- Sept 2022
• Pétur Aðalgeirsson, M.S. project, June 2022
• Manuela Fischer, post-doc, Sept -- Dec 2021 (Now Lecturer at ETH)
• Murilo Santos de Lima, post-doc, October 2018 -- November 2019 (Now in industry)
• Tigran Tonoyan, post-doc, June 2014 -- August 2019 (Now in industry)
• Christian Konrad, post-doc, Oct 2013 -- August 2016 (Now asst. prof. at U. Bristol)
• Ágnes Cseh, post-doc, January -- August 2016 (Now at Hungarian Academy of Sciences)
• Janne Korhonen, post-doc, January -- August 2016 (Now at IST Austria)
• Marijke Bodlaender, Ph.D. student, September 2012 -- 2015 (Now in industry)
• Kristján Valur Jónsson (Ph.D. from KTH, 2014), Thesis
• Pradipta Mitra, post-doc, 2010 - 2013, now at Google research, NYC.
• Elena Losievskaja (Ph.D., 2009), now at Sidekick Health. Thesis: Approximation Algorithms for Independent Set Problems on Hypergraphs. Now at AGR
• Unnar Þór Bachmann (M.S., 2009) : Thesis: Online algorithms for t-interval graphs.
• Ragnar K. Karlsson (M.S., mathematics, 2006), Thesis: Strip graphs. Now at CCP
• Haukur Þorgeirsson (M.S., 2005), now research professor in Icelandic manuscript studies at University of Iceland.

Some ancient stuff:

• Organized SIROCCO 2012 at Reykjavik University, June 2012.
• Organized ICALP 2008 !, in Reykjavik, July 6-13, 2008. (chair)
• Helped organizing MATCH-UP: Satellite workshop of ICALP 2008
• Invited speaker at NHC '06 , NHC Spring School and Workshop on Discrete Algorithms, Tokyo, Feb. 27 - Mar. 1,
• Subeditor for the Compendium on optimization problem detailing their approximabilities.
• Organized SWAT '96, here in Reykjavik. Hjalli has some pictures.
• The online version of the English-Icelandic Mathematics Dictionary, now available here.
• Webpage on the Subglacial Volcanic Eruptions in Vatnajokull 1996 and 1998.
• Colleagues on the web (not updated)

About Me

I then worked at Tokyo Institute of Technology for 8 months, followed by JAIST for three years in Japan. Since 1995, I have resided in Iceland, first at University of Iceland and since 2007 at Reykjavik University. I have also had visiting or other appointments: IBM Tokyo Research labs (1995), Max Planck Institute in Saarbruecken (1995), University of Bergen (1997-2000), Kyoto University (1999, 2007), Tokyo Institute of Technology (2005, 2013), and RIMS in Kyoto (2009, 2015, 2018).

Contact Information