Solving a 20-year math mystery to receive the Gödel Prize

“It is an unprecedented success,” says Martin Loebl, the head of the Department of Applied Mathematics at the Faculty of Mathematics and Physics, Charles University, regarding Hans Raj Tiwary, who has been awarded the Gödel Prize, one of the most prestigious awards in the field of computer science.

First of all, a huge congratulations for receiving the prestigious Gödel Prize! How did you find out about this award?

It's a bit of a funny story. The committee that announces the award is based in the US. That means there's a time gap. And that night I was sleeping in the same room as my kids and my daughter woke up around midnight and she had one of those kids' requests, you know, something nonsensical. I got a little annoyed and after making her sleep again, I was not sure I'd fall asleep. So I went to have a glass of milk and I opened the e-mail and found the message: “Congratulations, hasn't been not announced yet, but you have been selected for the Gödel Prize!” This was at 1:00 in the morning and then I could not sleep because it was so exciting and a little shocking. So, when my wife woke up and asked: “How did you sleep?” I had to say: “I slept for one hour, because I was waiting to tell you why I couldn't sleep anymore…” It was a shock because it's quite a prestigious award and was a little hard to believe. It still feels a bit unreal.

Was this award kind of your dream?

Maybe when I was 12 or 14. I wanted to study mathematics or physics when I was in high school, and you of course dream of getting the Nobel Prize or something like that. But then I moved to computer science and the equivalent of the Nobel Prize in computer science would be the Turing Award. So, there's always this fantasy but you know these are more like childlike dreams. You grow up and realize that these are exceptional things, you cannot count on them normally and you start focusing on doing math, because you like it. So, I wouldn't say that it was my dream, but not in the sense that I didn't want it, but it is not your reason why you are doing math.

What was the reaction of your colleagues? Anything surprising?

No, it was kind of expected. When I first received the e-mail, I was not allowed to tell anyone because it's announced a bit later. It was hard, I wanted to share but I could not. Then when it was announced my colleagues started sending congratulations, someone saw it on the announcement page, and they sent an e-mail to the whole department. And people replied it was nice, even maybe a little embarrassing.

The ceremony takes place at the 55th Symposium on Theory of Computing (STOC), which will take place in Orlando, Florida, next week. Are you looking forward to it?

Yes, unfortunately I will not go in person. This award is usually given out at one of the two conferences in either in STOC or in ICALP, which is like the European version. And this year it will be awarded in STOC. It's in the US. And by the time I got the notification, it was too late to arrange for a visa and other stuff.

The prize is awarded to a research paper that you wrote with four other colleagues. Do you have any ideas why the committee appreciated your work? What's the uniqueness of this study?

This paper that I wrote together with my colleagues from the Netherlands, Germany and Belgium received a lot of attention from the start. Right when we proved the result, we were pretty sure that it was a good result – we solved a 20-year-old problem. We sent it to STOC, which is kind of one of the two best conferences in computer science and usually just getting a paper accepted is a big honour. And our paper was nominated for Best Paper Award the same year, people were excited about it and it was clear that this was going to receive quite a bit of attention. Just last year, the same paper received again from stock a “test of time” award. For papers that have been published 10 years ago and are still kind of encouraging new research so this paper has a history of being appreciated. So, in that sense it was not too shocking to me that this paper was considered.

The paper is about combinatorial optimisation. Could you explain the main idea for the general public?

Sure, one of the basic problems that we deal with in computer science is how to make computers solve problems. The basic approach is you tell it as a series of steps which the computer follows exactly. This is called an algorithm – it is the recipe. And the biggest open problem, some people think it's not even solvable, is what are the problems that we can tell computers to solve quickly. There are some problems that are very difficult in this sense.

For example, if you wanted to make a road trip in the Czech Republic and you had selected 20 cities that you wanted to visit and you wanted to save on gas and unnecessary trips, you want to go there in the most effective and cheapest way.

So, this is roughly the “traveling salesman problem”, and it's a hard problem in the sense that every time I give you a map of the Czech Republic you will have to sit, look at the map, try some clever ideas and come up with a solution. Then if I give you a map of Germany with 20 different cities, you will have to start the whole process again. There is no recipe that once you know how to solve this problem, you can solve the different problems of the same kind.

Nobody knew whether we could tell the computer to do it well. People thought we couldn't, but we couldn't prove it. There are some limits to what it means to prove that something is impossible and there is a very specific way of solving problems, something called linear programming. Which is as general as possible. It is known that anything you can do reasonably you can do with this method.

So this was an old problem and we kind of proved that you cannot do it using linear programming in the sense you write one recipe, you give it a computer, and then you throw problems at it and you will keep solving it every time you throw a new problem. It will have to do something a bit clever.

Hans Raj Tiwary has been working at Charles University for the last decade. 

IT is a very progressive field. How unique is it that your work is still valid and receiving prizes even after 10 years?

There is one phenomenon that's common generally in life. If something gets popular, it gets more popular in time. If papers have a good initial reception, they tend to perform well over time. So I wouldn't say that this is a unique result in the sense that it's useful to researchers even after so many years. But let's say that the scope of it is a little bigger. It gets a lot more citations every year than other papers that I write. So, it's not very uncommon, but it's not super common either.

This paper has a negative result that says you cannot do something. The practical applications of such papers is that if you are trying to solve a hard problem don't try to solve it this way and we provided the theoretical explanation. In the past, people knew very well that these problems are probably not going to be solvable, so it's not that people would try to avoid it, but these problems kind of motivate people to try to make it more general.

What does it look like when you work? Do you use more paper or computers?

My work has let's say two phases. There are weeks when my mind is kind of black most of the time and I'm reading or watching videos not related to my work, but some general topic in mathematics or physics or whatever catches my attention. But then there are periods when I'm thinking about a problem, and then it's most of the day. It doesn't matter what I'm doing. This is in the back of my head when I go to bed, I'm thinking about this when I wake up the first thought is this problem. And occasionally when something looks promising, I take out the sheet of paper and try to write down something, work out some proof. Usually, it fails in silly ways. So, most of the time, I use just my mind. Then the second level is using pen and paper. Sometimes I also use computers if I have an idea, and I don't have a proof one way or the other, then I just write a simulation. But that is quite rare, so it's mostly pen and paper or nothing.

Do you have any scientific dreams or maybe a math problem that you would love to solve?

At the moment I'm stuck with one problem for maybe two or three years that I would like to solve. It's again related to the previously mentioned problem. There's a phenomenon called the cut polytope which is again kind of a map of the Czech Republic and there are highways and so on and you want to destroy the connection between two parts of the Czech Republic, but you don't want to spend too much energy. You want to break the connection in the cheapest way. I work on a problem called the cut quality of how many ways you can cut.

You have been working in Prague for the last decade. Would you like to stay in Prague for the foreseeable future?

I have never been attached to a specific place in my life, so practically if you transplant me from city A to city B and I managed to keep my friends and family, it doesn't make a lot of difference. In that sense when I moved to Czechia, I did not think about it much.

But after a few years, both my wife and I like the country and specifically Prague quite a lot. It's a very family friendly place. There are parks everywhere, policies related to childcare are nice. My colleagues at work are very helpful and friendly. And in general, my life is fairly fine, so I wouldn't say I'm not going to move from the Czech Republic, but I don't see any reason why I would. The only possibility might be my wife is from Spain and she gets a lot homesick so on and off, she would say: “I wish we were living in Spain”. But you know, as time passes, that gets more and more unreasonable dreams. I think we will stay here, but of course you can’t predict the future.

I know that your wife is also a scientist. What is the focus of her work?

She is also a mathematician. She is teaching at ČVUT in the computer science department, and she works in an area that's called computational geometry – it means solving geometric problems using a computer.

Do you understand each other’s work?

Yes, we have a fair bit of understanding. I can say that I would understand her work more easily because I have worked on those kinds of problems in the past. A very specific problem that she's working on at the moment I wouldn't know, but I understand the general area. One of my first papers that I wrote was in a conference called Symposium on Computational geometry. We discuss our science often, especially if we have a problem, we are stuck with or we want to run approved by someone So then we tell each other and discuss.