Teaching the computer how to think
When the conversation gets dull, Daniel Lokshtanov relaxes with tasks too complicated for computers to solve. That has made him one of Norway’s top algorithm researchers.
“My wife claims that I am not the best conversation partner. If a conversation gets dull, I tend to zone out and think about algorithms. I can see that that is not my most festive trait,” says Daniel Lokshtanov of the Algorithms Research Group at the Department for Informatics at the University of Bergen (UiB).
A love affair with mental exercise
The 32 year old researcher is already known as one of the top algorithm researchers. He has more than 90 publications at a high international level and has received the Meltzer Prize for young Researchers.
Since he first was exposed to the power of algorithms in upper secondary school, Lokshtanov has been thinking about numbers and formulas day and night.
“The day is filled with lots of spare time and I usually end up thinking about problems that have not been solved.”
An algorithm is a recipe to solve a problem. Without thinking about it, we are constantly presented with algorithms in our everyday lives. Algorithms sort the information when we are planning a trip online, and algorithms make sure the signalling systems work to prevent trains from colliding. The search to find the best algorithms is one of the biggest challenges in the field of informatics research.
How did you end up researching algorithms?
“Algorithms is the field in mathematics that reminds me most of mental exercise. What I like about it is that it presents me with problems that are easy to formulate, but hard to solve. ”
Like entering a boxing ring
Some tasks can easily be solved using a computer – like alphabetic name listing. Other tasks are too complicated for computers. This is where the algorithm researchers enter the picture. They are looking for structure and loopholes in sets of data, and if the algorithm can find this structure the data set can quickly be solved.
Lokshtanov and the other researchers only use pen and paper and old-fashioned brain activity as their tools. They solve problems that a computer would need thousands of years to solve. A lot of their work is hosting other algorithm researchers from throughout the world and study other researchers’ results.
“Our work can be compared to entering a boxing ring. The first time you enter, you might not be able to solve the problem. However, as you enter the ring again and again, suddenly you find the right solution.”
Lokshtanov enjoys being part of a solid work group, which has received several prestigious research scholarships from the European Research Council (ERC) and the Bergen Research Foundation (BFS).
“Already as a master’s student this innovative environment inspired me. The researchers are motivating each other to find solutions, and the environment is not too competitive. I have learned so much from my mentor, Pinar Heggernes, and I am looking forward to learn more from the top researcher and pioneer in algorithm research, Mike Fellows, who was recently employed by UiB.”
Hopes to benefit society - eventually
In 2010, Lokshtanov was selected for the BFS Recruitment Programme. He received a four-year grant of 13 million NOK (approximately 1.5 million Euros) for the project Beating Hardness by Pre-processing (BeHard).
“In this project we work on problems that no computer programs can solve efficiently, and then we try to solve these. It may seem as a self-contradiction, but it is not. We have a specific data set and we know that there is no computer program that can solve all such data sets efficiently. Nevertheless, it is possible that the data set we have can be solved. It becomes more interesting if we understand why this particular data set can be solved, and we can generalise the method to work for as many data sets as possible.”
“This grant was an important reason that I stayed in academia. I have been given great scope and the privilege to work with so many brilliant minds. ”
The aim is that the results from the mathematical models can be used in software.
“A lot of our work is not that reality-orientated, but we are hoping that the models can have benefits for society.”
Lokshtanov is also enjoying teaching the secrets of algorithms.
“Education is important – it helps me keep up to date in my work and challenges me.”
As an algorithm researcher Lokshtanov sees algorithms in everything.
“The only exception must be human behaviour, which is not always easy to predict and find patterns for. But as algorithm researchers we try anyway.”