Congratulations to Eva Rotenberg, associate professor in Computer Science at DTU Compute. She is among the 38 young researchers to receive a Sapere Aude grant from Danmarks Frie Forskningsfond/Independent Research Fund Denmark. The grant makes it possible for them to delve into their best research ideas while also building a research group around them.
Eva Rotenberg works in the research section Algorithms, Logic and Graphs (AlgoLoG). The section covers the core research areas of theoretical computer science and discrete mathematics. The research focuses on the foundations of computing with a broad impact in applied areas.
“It is always a great moment when the fund announces this year's Sapere Aude: DFF-Starting Grant recipients. These researchers are some of the best in their field, and they represent the future of Danish research. Especially in uncertain times, it is crucial to have talented researchers who can contribute with research-based knowledge across various fields,” says Chair of Independent Research Fund Denmark, Søren Serritzlew.
Text from DFF - Eva Rotenberg about her research and the starting grant.
Project: Dynamic Graphs: Distributed and Geometry.
What is your project about?
Efficient computations on big datasets is an exciting challenge that requires new mathematical insights and ideas. In this project, we will develop new algorithms for performing certain types of computations, and we will provide rigorous mathematical proofs that they are efficient and correct. The type of computation that is the focus of the project, is computations in graphs (the mathematical model for networks), and in discrete geometry. The project addresses the general question: How does one efficiently update one's knowledge about a graph or network, when it changes by connections disappearing and by new connections being formed? Aside from this being important on its own, because networks changes, it is also motivated because graphs are important as an underlying tool in many algorithms for computations on big datasets, and because the techniques developed to handle changes can lead to new insights into how one efficiently performs computations in parallel or distributedly.
How did you become interested in your particular field of research?
I am sure I am still in the process of becoming interested in my field of research; I keep discovering new interesting open questions, that are related to something within my expertise, and which I am itching to understand or maybe even attempt to solve. The concrete hypotheses in the project entered my radar of interest within the last couple of years, during which I, in collaboration with PhD students and postdocs, had made progress on some related questions and topics. The central over-arching question, on the other hand, of how to efficiently update one's knowledge about a changing graph, has had my attention for a bit more than a decade. Towards the end of my master of computer science education I chose to work on that topic, because I wanted to use mathematical methods in computer science.
What are the scientific challenges and perspectives in your project?
When a large graph or network changes, even by the addition or removal of just one connection, it may potentially have a large impact on its properties. In the field of Dynamic Graph Algorithms, we aim to not just accommodate one singular change, but seek to stand against a stream of small changes to huge graphs, while all the time understanding its properties. In order to efficiently update our knowledge about the graph or network, we carefully select partial answers to calculations, and store them in a structured way. When connections are formed or broken, we must on one hand be able to see which partial answers still hold, and, on the other hand, be able to efficiently update those that are no longer valid, so that we can combine them to form a new, correct analysis of the entire thing. To perform computations and analyses in such an updatable manner requires new mathematical insights. On a good day, this hunt for mathematical insights to solve computational problems is simultaneously difficult, beautiful, and fun.
What is your estimate of the impact, which your project may have to society in the long term?
Digitalisation and computations on big datasets play a considerable role in our society and in other sciences. But which properties do the results of these computations have? Are they transparent or explainable, in the sense that one can point to an explanation of their outcome? Do they protect private data, if such were part of the input to the computation? Are they as efficient as possible, or could a smarter algorithm have spent less time, energy, and space? Are they as precise as possible; do they give approximate answers because exact answers would probably demand infeasibly large computational resources? Such questions are addressed by Theoretical Computer Science. When we give new explainable algorithms and claim that they are efficient, precise, privacy protecting, and correct, we complement with proofs of said claims.
Conversely, we examine the impossibilities, and chart the computational hardness of algorithmic problems. The project at hand focuses on the resource consumption of efficient, correct, and precise computations.
Which impact do you expect the Sapere Aude programme will have on your career as a researcher?
The careers most affected by this grant are likely the two students who get the opportunity to obtain a PhD in algorithms and data structures via their employment on this project. Working with junior researchers gives me the chance to work on multiple different and related topics within my area of research. Learning something new is perchance my favourite activity, and when I work with other researchers (including junior researchers such as PhD students) I always feel that we are learning something new together.
In the long run, I want to be part of an effort to bridge the gap between the theory and practice of efficient computations in big datasets. An overarching goal that requires a multitude of participants and skills. With this grant, we, as a local research environment, take a step towards being able to solve that tremendous task.
