Václav Rozhoň: Science is a Social Process

What led you seven years ago to the renowned ETH Zurich, where Albert Einstein once studied?

I wanted to get the best education possible. Most of the top schools specializing in computer science are in the U.S. In Europe, there aren't as many—besides ETH, there's Cambridge or Oxford. ETH is not only a great school, but it's also relatively close—it's easy to travel from Prague to Zurich by night train. So, it was a fairly natural choice.

You studied at ETH alongside your wife (at that time your girlfriend). Both of you received a scholarship that is awarded to only about ten applicants per year in your field. How difficult is it to get into such a school?

It's hard for me to judge. It's definitely more difficult than getting into the Faculty of Mathematics and Physics at Charles University, but easier than being admitted to MIT or Harvard. If you enjoy computer science and have good grades, you certainly have a chance of getting into ETH. At least, that was the case for me.

What makes ETH so special?

Students at ETH have more opportunities—not just in their studies, but also in extracurricular activities. For example, I think it's easier to start a startup there. Partly because the university actively supports such initiatives in various ways, such as providing a space where students can work on their projects. But I also feel that an even bigger factor is the mindset. At ETH, you simply meet more students who are bolder when it comes to their careers.

As a researcher, it was extremely important for me to meet so many people at ETH who inspired me or even helped me with solving mathematical problems. It's simply a highly motivating environment. And that, in my opinion, is what truly makes great schools great. It's not just about the quality of lectures or the availability of workspaces for startups. It’s more about the atmosphere that constantly pushes you to think about what else you could be doing. Seeing the work of those around you inspires you and encourages you to think outside the box—to approach things in a way that isn’t necessarily conventional.

What specifically did this environment inspire you to do?

For example, my friends and I started a YouTube channel with educational videos about algorithms. It also led me to develop an interest in AI safety alongside my primary field of study. Artificial intelligence safety is a highly relevant topic, but so far, it has mainly been explored abroad. At ETH, and later at MIT, I met experts working in this field who inspired me to explore it as well. However, for now, it remains more of a hobby that I pursue in my free time.

There are different types of scientists—some dedicate their entire careers to a single topic, while others are always somewhat restless, trying to combine ideas and seek out something new. I belong more to the latter group.

Your primary field is theoretical computer science. What exactly do you do?

Theoretical computer science is a branch of computer science that is closely related to mathematics. I work on developing new algorithms, striving to understand them mathematically and compare which ones are better than others. Simply put, while programmers write code, we theoretical computer scientists sit in armchairs and invent new algorithms, which—if everything goes well—programmers then implement in practice.

That sounds like a dream job…

In a way, it is. Just as some people love beautiful music, I’m fascinated by algorithms and enjoy studying them. But it can also be quite frustrating—when you have a question and don’t know how to approach it, or when you don’t even know which problem to focus on.

There are different types of scientists—some dedicate their entire careers to a single topic, while others are always somewhat restless, trying to combine ideas and seek out something new. I belong more to the latter group.

How do you choose your research topics?

It’s definitely not as simple as waking up one morning and deciding: “This is what I’ll focus on.” For me, the people around me play a crucial role. I enjoy talking with colleagues, and from time to time, something meaningful emerges from those conversations. Personal connections also matter—a lot of it comes down to finding someone you get along with and communicate well with. Science is, in many ways, a social process.

Did you approach it the same way in the case of Dijkstra's algorithm, which you focused on in one of your recent papers?

Absolutely. I collaborated on Dijkstra's algorithm with several other researchers, including two Czechs—Jakub Tětek and Richard Hladík—whom I first met during my high school years at subject-specific competitions. Initially, Kuba, who until recently worked at the University of Copenhagen, and I were tackling a slightly different theoretical problem. Later, we explored where else our ideas could be applied. It occurred to us to focus on Dijkstra's algorithm, one of the oldest algorithms in existence.

What new insights can be gained about a nearly 70-year-old algorithm that computer science students learn about in university?

It may be surprising, but even for problems this old, there is still much to discover. Dijkstra's algorithm was developed in the 1950s, during the era of early computers and punched cards. It is one of the first algorithms designed for finding the shortest path in a road network. Imagine wanting to find the shortest route from point A to point B, say from Prague to Split. Today, all you need to do is open Google Maps, and within moments, you have your answer. Behind the scenes, various complex algorithms are running, but they are fundamentally based on the classical Dijkstra’s algorithm.

Algorithms vary in efficiency when solving problems, which is why we study and compare them. When theoreticians analyse algorithms, they often take a rather pessimistic approach—they imagine the most complex possible map and then calculate how fast the algorithm performs on it. This result is then considered the benchmark. This approach is known as „worst-case complexity.“ From a mathematical standpoint, this method is simpler, which is why it has been used for nearly 70 years. However, we decided to take a different approach and instead asked whether there exists an algorithm that operates optimally on every map.

So, you tried to be more optimistic…

And it turned out that this approach works—that this way of thinking fits well with Dijkstra's algorithm. We discovered that an efficient implementation of this 70-year-old algorithm can, in a certain sense, adapt to any given map and perform optimally on it. In the language of theoretical computer science, we would say that Dijkstra’s algorithm is „universally optimal.“ This was previously unknown and is quite a surprising finding.

Could this have any practical implications?

As much as I would like that to be the case, practice is always more complex than theory, and at this point, it is unclear how our ideas could be applied. In theoretical research, you often don’t know whether your findings will have practical significance in a few years. I would say that our result is interesting mainly because we tested a new approach and demonstrated that algorithms can be understood in a different way—not just through the standard pessimistic „worst-case complexity“ framework.

That brings us back to ETH, where you earned your Master and PhD degree. Thereafter, you spent a year at MIT. Where did you find it better to live and conduct research—Switzerland or the USA?

Both places were incredibly inspiring. MIT is an outstanding institution, with an even higher concentration of top-tier scientists, so from a professional and research perspective, my time in the United States was a very significant experience. On the other hand, life in America differs in many ways from life in Europe, and I had to adjust to quite a few things.

Such as?

For example, public transportation in the U.S. is nowhere near the level of what you find in Europe. Most people rely on cars, which didn’t suit my wife and me. Fortunately, in Boston, where we were both studying, cycling is a fairly convenient option, so we commuted to school that way. However, things were more complicated because, at that time, we already had a small child, so trips outside of Boston required quite a bit of planning. In this regard, life in Switzerland was much more convenient.

Last year, you and your family returned to the Czech Republic. Did you miss home?

A little, but above all, my wife and I realized that living abroad without family support is very challenging. In the Czech Republic, we have grandparents who help us take care of our son.

Since January, you’ve been working at the Institute of Computer Science at Charles University. Will your research continue in the same direction?

At the moment, I have several topics in mind that are similar to Dijkstra’s algorithm, specifically in the area of „instance optimality,“ a niche subfield of theoretical computer science where there is still room for new discoveries. Besides that, I’d like to apply my theoretical background to AI safety, though that will be a long-term endeavour. In this field—and in science in general—it’s quite difficult to predict what lies ahead…

Václav Rozhoň

Václav Rozhoň studied computer science at the Faculty of Mathematics and Physics at Charles University and theoretical computer science at ETH Zurich. He spent a year at the Massachusetts Institute of Technology in the USA and six months as a postdoctoral researcher at the Institute for Computer Science, Artificial Intelligence, and Technology (INSAIT) in Sofia, Bulgaria. Since January of this year, he has been working at the Institute of Computer Science at Charles University.

His research focuses on developing new methods for analysing algorithms, particularly in the field of instance optimality, which aims to bridge the gap between theory and practice in algorithm design. Last year, he and his co-authors received the Best Paper award at the FOCS conference for their research on Dijkstra’s algorithm, which was also covered by Quanta Magazine and Wired.

In his free time, he creates videos about algorithms for the YouTube channel Polylog.

Website: https://vaclavrozhon.github.io/.