Phd in the spotlight: Bruno Loff
On 21 January Bruno Loff (b. 1984) will be awarded his doctorate at the UvA. During his doctoral research at the Institute for Language, Logic and Computation (ILLC), he shed light on what’s known as the knapsack problem.
What did you do?
‘I looked for new algorithms. An algorithm is a recipe for solving a mathematical problem. Mathematicians are always looking for the most efficient algorithm. An inefficient algorithm costs a computer a huge amount of time and memory. My work included looking for better algorithms for what’s known as the knapsack problem.
This problem is based on the idea of a room containing items of a certain weight and a bag with a certain capacity. You need to get as much weight as possible into the bag. You could fill the bag with items of descending size until nothing else can fit in. But that strategy won’t work if you have an item taking up three quarters of the total capacity, and two items taking up half the capacity. That would mean you have to stop when the bag is just three quarters full.
Complexity theorists believe there is no efficient algorithm that can solve this knapsack problem. I’ve proven that in a particular field of mathematics, there is indeed no efficient algorithm to address the problem.'
Can you explain?
‘Imagine a large square containing every efficient algorithm. Mathematicians believe there isn’t a single algorithm in that large square that can solve the knapsack problem. I scrutinized a small section within that large square. That section includes all of what's known as the ‘efficient semi-algebraic parallel algorithms’. It’s indeed true that it contains no algorithms that can solve the knapsack problem.
I proved this using computer scientist Ketan Mulmuley’s ‘proof technique’. Proving a complete absence of any efficient algorithm for the knapsack problem in the entire square is a much more complicated problem, known as the ‘P versus NP problem’. This is regarded as the holy grail of my research area.’
You’ve since returned to Portugal, where you're from. Are you doing follow-up research there?
‘No. From March onwards I’m going to spend half a year meditating here in a house in middle of the woods. I started doing Vipassana meditation during my doctoral research. I found it very helpful.
There were many occasions when I wanted to abandon my doctoral research because I couldn’t get motivated. Meditation helped me persevere with it. It gives me stability and reignites my enthusiasm. I’ve also had lots of support from my supervisor, Harry Buhrman. Whenever I wanted to stop, he managed to convince me to carry on. I’m very grateful to him now for that.’
Will you return to research after that half year?
‘I’m not sure yet. This subject area, the computational complexity theory, is interesting but very theoretical. I also don’t know if being a researcher is the most fruitful way for me to use my skills. Maybe, maybe not. I’d also like to do something practical. I’ll be using the next six months to decide what direction to go in next.'
Author: Carin Röst