UiB fellow solves 20 year old math problem

Michal Pilipczuk at UiB’s Department of Informatics has solved a 20 year old mathematical riddle. His work can help computers to make better choices.

Two white boards filled with algorithms partially shown, from offices of the Algorithms Research Group at the University of Bergen.
WE HAVE THE NUMBERS: The Algorithms Research Group at UiB is heavily involved in basic mathematical research, but their work benefits the world outside academia as well. They use good old blackboards as much as modern technology to solve the riddles that computers can’t find the answer to.
Eivind Senneset

Main content

When using a Global Positioning System (GPS) to search for the shortest route between the Norwegian cities of Oslo and Bergen, a computer programme filters out irrelevant information. Hence you avoid suggestions to travel via London, Berlin, New York or even Cape Town.

The mathematical formula that defines the choice-making process in a computer programme is known as an algorithm. All computer systems are programmed using algorithms, which are mainly used to simplify a complex problem.

Providing better algorithms

“The better the mathematical theory that underpins the algorithm, the better the final algorithm will be,” says mathematician Michal Pilipczuk, who recently defended his PhD thesis at the University of Bergen’s (UiB) Department of Informatics.

Pilipczuk cracked a mathematical nut that the world’s top mathematicians had struggled for more than 20 years to crack. His solutions provide faster routes between non-intersecting destinations. This means better algorithms and helps the computer to suggest better options for future travel.

Computers don’t think

Pilipczuk’s mentor was Professor Fedor Fomin of UiB’s Department of Informatics, who is also a recipient of an ERC Advanced Grant and a prominent member of the university’s Algorithms Research Group. Despite the fact that Pilipczuk does basic mathematical research in its purest form, his work can make a practical impact.

“Computers do not think for themselves. We may think of computers now as rather advanced, but even new computers are still unable to solve certain algorithm problems that may seem trivial to most people,” says Fedor Fomin.

Good choices – or #fail

In some cases the computer may make a great choice, in other cases the computer may fail completely. E.g., there were many computers that didn’t manage the transition to the year 2000. Whereas the third world war that some predicted failed to materialise, certain prestige trains in Norway, such as the airport train in Oslo, ground to a halt.

“Even the smallest advances in basic mathematical research can have a major impact on the world. After all, we are surrounded by computer technology in modern society,” Fomin says.

(Translation: Sverre Ole Drønen.)