News

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: https://arxiv.org/abs/1901.02441

  • Published:
  • Updated:
Share
URL copied!

Related news

Photo: Aalto University
Research & Art Published:

Thermophotonics work receives EU funding

Exploratory research into waste-energy recovery awarded Horizon 2020 grant
Kuvassa vihreällä taustalla kuvat Matti Rossista ja Markku Kaustiasta
Research & Art Published:

Will the future bring pyramid scams like OneCoin?

Professors Matti Rossi and Markku Kaustia will discuss the opportunities and challenges of cryptocurrencies.
Professor Mady Elbahri
Honoured, Research & Art Published:

The German Society of Material Science awards Professor Mady Elbahri the DGM prize of 2020

The Deutsche Gesellschaft für Materialkunde e.V. (DGM) has recognized Professor Mady Elbahri at the School of Chemical Engineering, for his outstanding scientific achievements in the field of Nanoscience and nanotechnology.
Nainen seisoo ja katsoo sivulle hymyillen kädet puuskassa. Hänellä on päällään musta paita ja sininen huivi ja aurinko värjää taustaa vaaleaksi.
Research & Art Published:

Maarit Käpylä turned her childhood hobbies into a living

As a child, Maarit Käpylä was interested in the stars and coding, and now she researches the activity of the sun, which could not be done without computer science