Aalto researchers awarded for an article showing that algorithms cannot match more effectively than they do now

The prestigious conference, Foundations of Computer Science (FOCS) 2019, has given out the Best Paper Award to Jukka Suomela, Assistant Professor at Aalto University Department of Computer Science, and his colleagues. FOCS is one of the two major conferences in the field of theoretical computer science.

The title of the article is Lower bounds for maximal matchings and maximal independent sets, and computer scientists have studied its topic, matchings, extensively for decades. One of the most fundamental questions in computer science is what types of processes can be automated effectively. In the research project in question, Suomela’s group looked at the topic from the perspective of distributed computing, and they wanted to figure out what types of tasks in a network can be solved effectively. ‘Matching is an example of such a task,’ says Suomela.

The key question about matchings is how far one needs to see from a single node in order to find a pair for it in the network. Suomela and his colleagues show mathematically that looking at the local neighbourhood of the node is insufficient and matching cannot be done more effectively than current algorithms do.

Even though this study is theoretical basic research, the matching problem can be made more understandable by using a simplified situation in which employers need new employees and job seekers need new jobs. In other words, employers need to be matched with the right job seekers.

One way to solve this problem is to use a centralized service that contains information about all job seekers and open vacancies, but the problem of matching can also be solved by using a decentralized, local approach. In the aforementioned example, a job seeker would list all jobs they find interesting and approach them systematically, one by one. Such a method is, however, slow and researchers have long been interested in how effectively algorithms can match.

In their article, Suomela and his colleagues proved that any method aimed for matching is either slow or inevitably leads to a wrong solution. These results indicate that the development of algorithms designed to solve these types of problems has reached a point in which researchers can show that current methods are the best or almost the best possible solutions. ‘We managed to set boundaries for how effective methods can exist. We found out, for example, that one method that was developed in 2001 is, in given situations, the best possible approach. It’s truly impossible to speed it up.’

Suomela worked together with Aalto University postdoctoral researchers Alkida Balliu, Juho Hirvonen, Dennis Olivetti and Mikaël Rabie and postdoctoral researcher Sebastian Brandt from ETH Zürich. The Academy of Finland funded their research.

The FOCS Best Paper Award is one of the most appreciated awards in the field of theoretical computer science. ‘It’s very unlikely that I would receive anything this big for another time in my career. In our field, everyone will speak about maybe five topics this year, and this will be one of them. It means very, very much to me,’ says Suomela.

Link to the research article: https://arxiv.org/abs/1901.02441