Magnus M. Halldorsson

News and Events

• Paper on fast distributed degree+1-coloring algorithms (Dec'21)
• Best paper award at SIROCCO'21
• Paper on improved distributed coloring algorithms (May'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. One area of major focus has been wireless communication, particularly on combining rigorous algorithms analysis with realistic models of interference. Current main focus is on distributed algorithms, particularly for coloring.

In the past, I have had interests in bioinformatics and biological computing, security, and the sociological aspects of a networked world.

Online papers: Wireless Algorithmics -- Algorithms and Complexity -- arXiv

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

• Alexandre Nolin, post-doc, February 2020 --

Alumni

• Murilo Santos de Lima, post-doc, October 2018 -- November 2019 (Now at Leicester)
• Tigran Tonoyan, post-doc, June 2014 -- August 2019 (Now at Technion)
• Christian Konrad, post-doc, Oct 2013 -- August 2016 (Now asst. prof. at U. Bristol)
• Ágnes Cseh, post-doc, January -- August 2016 (Now at Potsdam and Hungarian Academy of Sciences)
• Janne Korhonen, post-doc, from January -- August 2016 (Now at IST Austria)
• Marijke Bodlaender, Ph.D. student, September 2012 -- 2015
• Pradipta Mitra, post-doc, 2010 - 2013, now at Google research, NYC.
• Elena Losievskaja (Ph.D., 2009) : 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 faculty member 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