Magnus M. Halldorsson: EATCS Fellow 2020

As announced here, the EATCS Fellows vintage 2020 are

• Pierpaolo Degano, Universita di Pisa, Italy: for his contributions in concurrency theory and applications in security and for biological systems. 
• Mohammad Taghi Hajiaghayi, University of Maryland, USA: for his contributions to the theory of algorithms, in particular algorithmic graph theory, game theory, and distributed computing. 
• Magnus Mar Halldorsson, Reyjavik University, Iceland: for his contributions to the theory of approximation and graph algorithms as well as to the study of wireless algorithmics. 

Congratulations to all of them! However, I trust that Mohammad and Pierpaolo will forgive me if I devote this post to celebrate Magnus, his work and his contributions to the TCS community.

So, why was Magnus chosen as one of the EATCS Fellows 2020? Here are some reasons why.

Magnús has offered seminal contributions to the theory of approximation and graph algorithms as well as to the study of wireless algorithmics. His research career and contributions so far can be roughly divided into two phases. The first phase spans the time from the beginning of his career until roughly ten years ago. During that time, Magnús made significant contributions to approximation algorithms for maximum independent set and graph colouring, amongst many other problems. In the second phase, which started a bit more than ten years ago, he has worked on the algorithmics of realistic models for wireless computation. I think that it is fair to say that Magnús is currently the expert on wireless algorithmics based on the SINR model.

These two phases are not at all disjoint. Indeed, the typical problems studied in the SINR model, such as determining the capacity of wireless networks or how to schedule messages in such networks, can be seen as independent set and colouring problems, respectively, and his experience with those problems in graph algorithmics certainly helped Magnús in obtaining breakthrough results in wireless algorithmics. Throughout his career, Magnús has also given significant contributions to the computation of independent sets and colourings in restricted computational models, such as the online model of computation and the data streaming model. His sustained research productivity, both in quality and in quantity, is all the more remarkable since it has largely been achieved working in the difficult research environment in Iceland, where he was largely isolated until the establishment of the Icelandic Centre of Excellent in Theoretical Computer Science (ICE-TCS) in 2005. (Magnus has been the scientific director of the centre for 15 years.)

In addition to his seminal research achievements, Magnús has served the theoretical computer science community by sitting on prestigious award committees, organizing conferences and workshops in Iceland and elsewhere, serving on steering committees and by acting as an inspiring mentor for young researchers in computer science who have come to Iceland explicitly to work with him. By way of example, Magnús is a member of the steering committees for SIROCCO (chair), ALGOSENSORS and SWAT, Scandinavian Symposium and Workshops on Algorithm Theory (chair). He was a member of the Council of the EATCS and has organized the best attended ICALP conference to date (ICALP 2008). Amongst many other such duties, he was PC chair for Track C of ICALP 2015 and of ESA 2011.

Magnús was also one of the initiators and first editors of “A compendium of NP optimization problems”, which is catalog of approximability results for NP optimization problems and has been a useful resource for researchers in that field for a long time.

Summing up, Magnús is a true stalwart of the algorithmics research community, and a great example for many of us. In my, admittedly biased, opinion, he richly deserves the recognition of being named an EATCS Fellow. I have no doubt that he will continue to lead by example in the coming years.