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

Jukka Suomela and his colleagues prove that any method designed to find a matching is either slow or leads to a wrong solution.
Jukka Suomela Research Group
The awarded article was co-authored by postdoctoral researchers Juho Hirvonen, Alkida Balliu and Dennis Olivetti together with assistant professor Jukka Suomela.

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:

  • Published:
  • Updated:
URL copied!

Related news

ARTS open science roadshow, pic of the session
Research & Art Published:

European Open Science Cloud (EOSC) Finnish Forum webinar on 25th January

One of the speakers is Karel Luyben, the first president of the EOSC Association and a member of board at Aalto University.
Installation Talk 2020, Jarkko Niiranen
Research & Art Published:

Professor Jarkko Niiranen on the computational mechanics of microarchitectural solids and structures

'When developing models, we spend a lot of time on mathematical physics, numerical mathematics and computer programming, but the fundamental concepts of mechanics remain the same' says Niiranen in his installation talk.
A photo showing Dr. Dorothea Golze
Research & Art Published:

Computational physicist Dorothea Golze receives prestigious Emmy Noether Award

Dorothea Golze received funding from the German Research Foundation within the Emmy Noether Programme to establish her own junior research group at the Technical University of Dresden.
Dronen ottama kuva Otakaari 1:sestä, kuva: Mikko Raskinen
Research & Art Published:

How do you know where a drone is flying without a GPS signal?

In Jouko Kinnari's doctoral dissertation, the location of a drone can be determined using map data and sensors.