On September 29, 2022, the GI Dissertation Award 2021 was presented to three exceptional winners at Informatik 2022 in Hamburg. TU Wien Informatics’ Markus Hecher, post-doc researcher at the research unit for Databases and Artificial Intelligence was honored for his thesis “Advanced tools and methods for treewidth-based problem solving”. The prestigious prize is awarded by the Gesellschaft für Informatik e.V. (GI), together with the Schweizer Informatik Gesellschaft (SI) and the Österreichische Computer Gesellschaft (OCG). The winners can look forward to a prize money of 5000 Euros.

Christine Regitz, President of the German Informatics Society (GI) was excited “to see which complex and relevant problems researchers already tackle in their Ph.D. theses. […] The GI Dissertation Award aims to put a spotlight on them and their contribution to computer science. After all, they are not only drivers of innovation, but also important figureheads of European computer science research.” Further awardees are Alejandro Molina Ramirez from TU Darmstadt, and Moritz Lipp from TU Graz.

Treewidth-based algorithms in AI: Solving an unanswered problem

Markus Hecher finished his Ph.D. in July 2021 within an individual binational agreement between TU Wien and the University of Potsdam, supervised by Stefan Woltran and Torsten Schaub.

In his thesis, Markus Hecher focused on ways to improve solving computationally hard problems. In order to speed-up modern computer programs tackling such problems, one can analyze the structural dependency of instances. This is often studied by means of the so-called treewidth, a measure that indicates how tree-like (i.e. how easy to solve) an instance is. Hecher developed a novel toolkit for ruling out significant improvements of a whole list of treewidth-based algorithms in AI, thereby solving a problem that has been unanswered for more than a decade.

Besides the GI Dissertation Award, he received the EurAI Dissertation Award 2021, the National Award of Excellence 2021 by the Federal Ministry of Education, Science and Research (BMBWF) and was shortlisted for the Heinz Zemanek Award 2022 by OCG Austria and the E.W. Beth Outstanding Dissertation Prize 2022. For a single-authored paper covering a key result of his thesis, he has been awarded the prestigious Marco Cadoli Best Student Paper Award at KR 2020. Moreover, a recent follow-up work resulted in a combined Best Student Paper Award and Best Paper Award at ICLP 2021.

Markus Hecher has set the course for an extraordinary academic career – after receiving the FWF Erwin Schroedinger Fellowship he is now carrying out 2 years of research at MIT, Massachusetts (USA) in the group of Erik Demaine. He is currently working on a book based on his thesis, which will be published in the IOS Press Dissertations in AI Series. Read more about his recent projects and publications here.