Congrats Magnus!Yesterday I visited Denmark's beautiful Odense to join the doctoral committee of Magnus Berg Møhring together with Rob van Stee and Lars Rohwedder. Magnus has done some fantastic work on online algorithms with predictions, advised by Kim Skak Larsen, Lene M. Favrholdt, and Joan Boyar. 
photo by Michael Steensen Next to studying how well predictions can be utilized for well-studied graph and resource allocation problems, Magnus' main contribution is building up a complexity theory that is centered around a parameterized version of Asymmetric String Guessing and based on a kind of prediction-preserving reduction. Both hardness and membership (and thus completeness) results have been established for a large number of natural problems, introducing some structure into the study of online algorithms with predictions. Further Reading
|