Sándor Kisfaludi-Bak asks the tough questions through computational geometry

What is your research about?

Computational geometry is about the interaction of two fields: geometry, which is a branch of mathematics that goes all the way back to the Ancient Greeks, and computation, the study of automated solutions, especially algorithms. The gist of my research is about developing fundamental knowledge of geometric structures in some of the most challenging problems theoretical computer science can offer.

To put it simply, it’s about how we can solve problems involving points, lines, polytopes, curves, or any kind of geometric construct using a computer. Such an understanding allows us to propose theorems for the most optimal algorithms.

These kinds of theoretical guarantees can then be used by computer scientists in more practical applications. As a theorist, I’m quite cautious with overstating the practical solutions that may arise from computational geometry, for some theoretical contributions trickle down to practical work very slowly. On the other hand, there are plenty of theoretical insights that find their place in the real world very quickly.

How did you get into science and your field of research?

I think the ethos of science was in me from an early age. I was always very interested in the world around us and the unknown. The best way to understand the unknown is to probe it, which I began to do in high school, through math. I loved problem-solving and it eventually led me to programming in my teenage years, writing bits of Pascal code for fun.

I followed my love for mathematics to the Eötvös Loránd University and began to realize that I was more drawn towards the abstract and fundamental questions, in contrast to the practical questions that a software engineer would solve. Creating longer, and more complicated programs, was perhaps a bit too hands-on for me as it didn’t really fit my thirst for fundamental knowledge and algorithms.

I completed my university degrees with a focus on discrete mathematics and combinatorics, which go hand-in-hand with algorithms. But the prospect of pursuing an academic career blurred a bit – it didn’t seem like the sort of work that I had imagined it to be, but nevertheless decided to give it a shot.

Looking back, I’m glad that I did, because during my postgraduate studies at the Eindhoven University of Technology, I finally felt at home. The community and professors showed me the side of academia that I wanted to be a part of and the power of collaborative research. In this environment, my journey in math and in the theory of algorithms began to bear fruit as I delved deeper into geometric network problems.

My dissertation included our first results on the Euclidean travelling salesman problem, and I was awarded with the Distinguished Dissertation Award by the European Association for Theoretical Computer Science.

What brought you to Aalto?

During my academic journey, I’ve seen professors on the brink of burning out and not being able to focus on research nor teaching. But I’ve also seen professors who were inspiring and who have managed to maintain a healthy work-life balance while also engaging their students and producing quality research.

Through these experiences, I’ve developed an appreciation for collaboration and colleagues – research and discovery are fun only if they can be shared with others. If someone is working on the same thing, I’d rather work with them, not against them. Hence, research should be about collaborating, and Aalto has the international gravitas to attract talented people with whom we can build engaging and influential research groups.

I hope to bring a flair of geometry to the Theoretical Computer Science group here and to introduce students to the sheer beauty of it. Computational geometry is a subfield which hasn’t been that prominent in Finland yet, but which is a very important toolset in research on algorithms. It’s a different, yet natural, way of thinking about problems due to its visual nature.

What do you consider as a highlight of your career so far?

My colleagues and I just published a new paper on the approximation schemes for Euclidean travelling salesman problem at the IEEE Symposium on Foundations of Computer Science, which is considered one of the top academic conferences in the field.

The problem is based on the simple question of what is the shortest round trip that visits all given points on a plane? It’s considered a hard problem in our field, so to solve it efficiently, we need to settle for approximate solutions, that is, tours that are slightly longer than the shortest tour.

The better approximation we want, the more time we should be willing to spend on running the algorithm. Our paper gives a new algorithm for approximating the problem that exhibits the best trade-off yet between the quality of the approximate solution and the running time.

We also prove that the trade-off we achieved is optimal under standard complexity-theoretic assumptions. Moreover, our research has driven progress on the problem for the first time in two decades.

What are you romantic about in science?

I think geometry is beautiful, and gathering knowledge is how humanity ultimately survives.