Travelling at the speed of algorithms

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 used to resolve a complex problem automatically, or at least to simplify it so that it becomes more graspable,” says mathematician Michał Pilipczuk. “The better the mathematical theory that underpins the algorithm, the better the final algorithm will be.”

The Polish national is a member of the Algorithms Research Group at the University of Bergen’s (UiB) Department of Informatics at the Faculty of Mathematics and Natural Sciences. Before arriving in Bergen, Pilipczuk held master’s degrees in mathematics and informatics from the University of Warsaw.

Young and gifted researcher

In November 2013 Pilipczuk successfully defended his PhD thesis at UiB. Obviously not only the disputation committee were overwhelmed by this young researcher. Also the jury of the Meltzer Prize were so impressed by the 25 year-old mathematician and recent graduate that he became one of two recipients of the 2013 Meltzer Award for young researchers. He received the award in March 2014.

The jury praised his exceptional work and went on to say:

“What makes Michał's work exceptional is not the short time it took him to get his PhD degree (in two years, with teaching duties), but the depth and the diversity of his research. His contributions to research within theoretical computer science are equivalent to several PhD degrees. The number of exceptional results that he has contributed to are not only outstanding for a young researcher but are exceptional even for internationally acknowledged professors in their most productive years.”

Faster and better routes

Pilipczuk solved a mathematical problem that the world’s top mathematicians had struggled for more than 20 years to crack. No wonder then that he was once a member of the Polish team at the International Mathematical Olympiad.

“My research will serve to create solutions that provide faster routes between non-intersecting destinations. This means better algorithms, and helps the computer to suggest better options to find routes between multiple sources and destinations that do not cross,” says Pilipczuk.

In the future, this research could be useful when travelling; helping cut travel times. However, more short term, Pilipczuk sees great economic gains in the computer industry, and in particular so-called very-large-scale integration (VLSI) design.

Great commercial potential

In hardware manufacturing there has been great interest in theoretical results on such problems for the past 20–30 years. This obviously shows the great commercial potential for the work done by Pilipczuk and his research partners.

“Suppose you are a company that designs computer chips, or motherboards,” explains Pilipczuk, describing the latter as a flat piece of plastic on which all the different guts of a PC are placed.

“On the chip/motherboard there are multiple devices that you want to connect by wires. For instance, on the motherboard you want to connect the processor with the graphic card and with the network card, the network card with the output to an antenna, etc. However, as the motherboard is flat, the wires cannot cross, or otherwise the cost of manufacturing would get much higher; a similar problem happens for chips. Hence you want to design the chip/motherboard in such a manner that the devices get connected, but the wires do not intersect.”

The results were co-authored by Pilipczuk with three other researchers: Marek Cygan (University of Warsaw), Marcin Pilipczuk (then University of Warsaw, currently UiB), and Dániel Marx (Hungarian Academy of Sciences).

Computers don’t think

Pilipczuk’s PhD 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 Bergen Algorithms Research Group. Despite the fact that Pilipczuk does basic mathematical research in its purest form, his work can have 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., many computers 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,” says Fomin.

Facts about the Meltzer Award

• The Meltzer Award is named after Lauritz Meltzer, who was a Norwegian engineer, officer, industrialist and philanthropist.
• The award is annual and awarded by the Meltzer Fund, who also sponsor research projects and travel grants for researchers.
• The award ceremony takes place every year on 8 March, Meltzer’s day of birth.
• The fund aims to promote research activity at the University of Bergen in particular, but also awards grants to applicants from other Norwegian universities or other science institutions.

(Translated from the Norwegian by Sverre Ole Drønen.)

This article first appeared in the UiB Magazine 2014/2015. You can download a PDF of the full magazine or you may browse the magazine online.