Award winning algorithm research
Interview with Jan van den Brand
Jan van den Brand is the winner of the 2021 EATCS Distinguished Dissertation Award. Read about his algorithm research, the news in this field and which problems he would like to solve in the future
In July, Jan van den Brand received the 2021 EATCS Distinguished Dissertation Award. The ceremony was held at the 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) in Paris, France. Read his thoughts on winning the award.
How does it feel to get this recognition within your research field
and be selected as a winner of the 2021 EATCS Distinguished Dissertation Award?
"When I got the news, I was very excited and it was hard not to tell friends and family about it until the public announcement. I am thrilled and honoured to receive the award, but it also adds some pressure. I want to demonstrate that this was not a one-time thing and that I can maintain this level of research."
Briefly, can you tell us a bit about your research?
"My research is on algorithms, and these are step-by-step instructions for computers to solve specific problems. In my research, I try to find algorithms that require fewer steps so that computers can solve problems in less time.
My focus here is on algorithms that solve dynamic problems. An example would be map services like Google maps or Apple maps, which can tell us the fastest routes on the road network while there are changing traffic conditions. I generally study problems where computers must maintain some solution while the underlying structure changes over time."
What excites you the most about your area of research?
"Research in theoretical computer science is a lot like solving puzzles. Coming up with the right answers is tricky, but there is a moment when it clicks, and the answer becomes apparent. It is very rewarding when some problem initially seems impossible to solve, but then you find some concise, elegant approach that looks almost obvious in hindsight."
What do you think is the most exciting research going on right now within your field?
"Very recently, a new algorithm for the maximum flow algorithm was discovered by Chen et al. The maximum flow problem asks how much flow can be routed through a network if the connections in the network have maximum capacities. This problem has been studied for over a century. In a sense, this problem is older than the field of computer science. I also worked on this problem in my thesis and got optimal results for some exceptional cases, but this new result by Chen et al. essentially settles that line of research.
If you want to read more about this, here is an article in Quanta magazine about this result .
What problems do you hope to solve with your research in, let’s say, 5 or 10 years?
"A significant problem is to understanding sparse structures better. To briefly explain sparsity, consider a social network with millions of users, where we think of friendship as a connection in the network. In the worst-case, everyone could be friends with everyone else, so there could be billions of connections. This would be called a "dense" network. In practice, however, the average user has a few hundred friends, so the number of connections in the network is much smaller than the hypothetical worst case. We call such a network "sparse".
This and similar notions of sparsity come up in many problems, where in practice, a problem might have a lot of variables (e.g. users). Still, the number of dependencies (e.g. friendships) is relatively small. Some of the theoretically fastest algorithms are only good for "dense" problems but not for "sparse" ones as they occur in practice."
Paper name: Dynamic Matrix Algorithms and Applications in Convex and Combinatorial Optimization. Advisor: Danupon Na Nongkai
Related news
Studying traffic flows in Kista to reduce emissions
To better understand emissions from traffic, researchers will use big data and AI to study traffic flows in Kista. The hope is to create transport solutions that generate lower emissions and reduce th...
Read the articleFrustration over parking fines led to action
A frustration with parking fines led to the development of a parking app that can read signs and help avoid fines. Now KTH students Maximillian Claesson, Industrial Engineering and Management, and Zak...
Read the article