Ioana-Oriana Bercea new assistant professor in Algorithms and Complexity at KTH

Ioana, what are your research area, research interests, research methods, and application area?

I specialise in basic research in algorithms and data structures. I believe this is a beautiful field, in which we view problems abstractly and can use creativity and mathematics to develop algorithms that are guaranteed to work well. The idea is that by adopting a high-level view of problems, we can gain insights and provide principled approaches that we can then prove will work for a variety of more detailed scenarios. 

Lately, my interest has been in designing data structures, which are methods of organizing data in hardware to gain efficient access to it. My focus has been the design of data structures that can handle large amounts of data without compromising the performance. This is especially interesting now as we gather and process data in exponentially increasing amounts. In this context, one perpetual challenge is to ensure that the underlying computing infrastructure, that stores and indexes this data, does not become a bottleneck in terms of the time, energy, and hardware spent accessing the data.

What do you think are the large research challenges in your research area and why?
The questions that my field asks are quite old and yet they continue to be relevant since modern hardware keeps evolving and new application domains continuously emerge. In this sense, I think one of our future challenges is that of updating the theoretical frameworks, such as machine and data models, that we rely on to argue about the efficiency of our proposed data structures. In some sense, efficiency is in the eyes of the beholder, and I think we should maintain a constant conversation with the applied side to make sure that we say things that are interesting not just theoretically but also practically. For instance, one parameter we must be mindful of in the future is the energy cost of our data structures.

If you are looking for some research collaborator(s), what competence are you looking for?
I am curious about the kinds of data my colleagues are storing and accessing, and how they would like to optimise the performance of their data structures. My experience has been that there are very interesting problems hidden “in the wild”. Problems which either theory is unaware of, or in which a bit of theory can make a lot of difference. I am also curious about hardware implementations of data structures, especially after seeing some movement on this front in the startup scene. I am looking for colleagues who are curious about these questions and willing to meet me halfway between the theory and the practice.

Can you tell us more about one of your research results and why you picked it?
I’ve done research on some of the most basic data structures that have been formalised, so basic that they are taught to every Computer Science Bachelor’s student: hash tables. I would like to mention, however, another fundamental and related problem, that of perfect hashing. This is a problem that is particularly close to my heart as it kept me motivated during the Covid lockdowns and has had a significant impact on my career. It is joint work with Professor Guy Even, who was my host during my postdoc at Tel Aviv University. 

One way to understand perfect hashing is to recall a famous thought experiment from Mathematics: Hilbert’s infinite hotel. The idea is to imagine an infinite hotel that is already full and then consider what happens when another guest arrives. Despite being full, the hotel can still make room for this new guest by moving the guest from room 1 to room 2, the guest from room 2 to room 3, and so on. How is this related to data structures? We can think of guests as data and then ask for a way of assigning items to rooms, or memory addresses, such that no two items are assigned the same address. We want to do this fast, without going through the data, and without allocating much more memory than is necessary for storing the data. This is perfect hashing in a nutshell. The particular challenge that Guy Even and I addressed was how to make room for a new guest without moving all the other guests around, which was previously believed to be impossible. We showed that it is possible, and along the way, described a unified view of several of these fundamental data structures, including hash tables.

Lastly, what do you like with Sweden, Stockholm and KTH?
I really admire the Scandinavian lifestyle and the values of trust, balance, and responsibility that Sweden embodies. Most importantly, Sweden and KTH put their “money where their mouth is” and it is a privilege to be part of a society that actively works to get better. The passion and excellence of my colleagues and students at KTH continually inspire me. Stockholm is a wonderfully diverse and vibrant city that I believe will always be exciting.