Magnús M. Halldórsson

News and Events 2023

• Spotlight talk at WOLA 2023, 7-9 August, MIT
• Program chair for PODC 2023
• Invited speaker at Optimization and Algorithms (OPAL), Veszprém, Hungary, 5-9 June 2023
• Recent papers:
  • A Distributed Palette Sparsification Theorem (with Maxime Flin, Mohsen Ghaffari, Fabian Kuhn, Alex Nolin)
  • Fast Coloring Despite Congested Relays, in DISC'23 (with Maxime Flin,Alex Nolin)
  • Coloring Fast with Broadcasts, in SPAA'23 (with Maxime Flin, Mohsen Ghaffari, Fabian Kuhn, Alex Nolin).
  • Fast distributed Brooks' theorem, in SODA'23 (with Yannic Maus, Manuela Fischer)
• Talk: [April 2023] "Distributed graph coloring: The loglog-revolution" at RIMS, Kyoto University
• Project funded by the Icelandic Research Fund: Constrained Distributed Symmetry Breaking

News 2021 - 2022

• Elected EATCS Fellow
• Best paper award at SIROCCO'21
• Paper on fast distributed degree+1-coloring algorithms in STOC'22.
• Paper on fast distributed coloring in CONGEST in STOC'21
• Talks:
  • [8 Dec 2022] "Distributed graph coloring: The loglog-revolution" at NestID seminar
  • [29 Nov 2022] "When can we color fast?", workshop honoring Pierre Fraigniaud
  • [18 Nov 2022] "Local Brooks' Theorems" at George Mason University combinatorics seminar
• Stepped down as Steering Committee Chair for SWAT (Scandinavian Conference on Algorithm Theory) after 19 years

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. (Now at CISPA, Saarbruecken)
• 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 Senior Lecturer at University of 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., 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.
• 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