Computer scientist Professor Piotr Sankowski from the University of Warsaw is looking for algorithms that would work best regardless of the circumstances. His work may contribute to the development of modern computer science.
THE EUROPEAN Research Council (ERC) is one of the most important and prestigious institutions to offer grants to researchers. Prof. Piotr Sankowski from the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw belongs to a small group of scientists who have received an ERC grant more than once.
His first grant was for designing and analysing approximation algorithms for problems whose precise solution is impossible due to the excessive time the calculations would take. The second grant concerned the commercialisation of the results. The latest one (amounting to more than 1.5 million euros) is funding a research project entitled ‘Towards Unification of Algorithmic Tools’. Its objective is to develop universal algorithms.
An algorithm is…
PROF. PIOTR SANKOWSKI: …a list of instructions for the computer that informs it how to perform simple tasks in order to ultimately carry out more complex operations. Different problems require different instruction sets.
And a universal algorithm?
It’s an algorithm that is as good as possible regardless of the given problem’s details. Let’s assume that we have one problem to solve, e.g. multiplication. The thing is, today we can imagine ten different algorithms prescribing how the computer is supposed to multiply, but we can’t select the best algorithm, because each of them is good in a different case. One algorithm works best in practice. Another is better, but only in theory. The next one works best for specific numbers, and so on. That is why using algorithms is difficult, because you need to be an expert to know which algorithm should be used in a given case. In addition, the newest and best algorithms are hard to apply, so essentially people don’t use them. The reason for this problem is that we have no universal solutions.
Your team is trying to develop such universal algorithms. What problems are they supposed to solve?
We are focusing on three areas. First, we want to design universal algorithms for static graph problems. A graph can be compared to a road map with roads and crossroads. One of the simplest problems that algorithms can solve on graphs is to look for the shortest route from point A to point B.
The second area are online problems. The situation is different here, because we don’t have all the data. If we take our road map again, in this case we find out the road has been suddenly closed. The new algorithm has to deal with uncertainty about the future. The third area involves using additional properties of data.
What does that mean?
Let’s get back to the example with finding the shortest route. It can turn out that this problem should be dealt with differently if we are thinking of Europe’s road map and differently if it’s Africa’s. That’s why one algorithm works best for the road map of Europe and another – for the road map of Africa. What we want to achieve is to develop a universal algorithm, which would be able to use these special data properties.
Can your research have an impact on the work of IT specialists?
Although better and better algorithms are created all the time, they are not widely used because they are so complex that no one knows how to use them. We want our solutions to be simple and universal. We hope that our research will affect the practical use of algorithms.
University of Warsaw
POLISH IT STUDENTS REGULARLY WIN MEDALS AT IT COMPETITIONS
A real sensation is the team from the University of Warsaw, which has been in each of the last 25 finals of the International Collegiate Programming Contest– the oldest and most prestigious IT contest for students. Altogether, computer scientists from University of Warsaw have won the world championship twice and collected fifteen medals up to 2019. Other Polish teams are successful as well. The Jagiellonian University has entered the finals twelve times in total and has won three medals. The University of Wrocław has been in the finals eleven times and has won three medals, and the AGH University of Science and Technology in Kraków and Poznan University of Technology have both reached the finals once.
