[SENSIBILITÉ] A new ERC project at EURECOM on the fundamental theoretical foundations for new generation networks
In the context of future generation wireless networks, reducing transmission load is crucial for communications in practice. To achieve that, a necessary approach is to focus on the fundamental theoretical foundations of such networks. EURECOM’s Professor Derya Malak, was awarded an ERC starting grant, for her project SENSIBILITÉ, in order to understand how we can use communication networks for computational purposes, working at the intersection of information theory and computation. In other words, what is the minimum possible amount of bits that we need for the computations and transmissions to be able to achieve a desired computation task over a network?
Q. Congratulations on your ERC Starting Grant! What were the steps that lead to this success?
DM. The factors that led me to succeed in this grant have roots in my postdoc, when I started envisioning the research problems I would be passionate about working on in the coming years, which I still do. Most of my days, I sat down or got up and thought about these problems in depth, which motivated me to write them down. It was a challenging but inspiring process, writing my research vision for the coming years toward developing a solid communication theory that explores the fundamental limits of computation in networks! There were some very hard-working couple of months significantly devoted to this proposal. The best part is to be awarded this grant and to be able to continue working on the problems that truly inspire me.
I gained valuable feedback when I submitted -unsuccessfully- a premature version of this project to an NSF call during my time in the US. However, since my arrival at EURECOM last year, there has been a significant development towards the maturation of this project proposal. I also received extensive support from our faculty and the director, as well as other external consultants on the non-technical aspects.
Q. Could you briefly describe the context of your project SENSIBILITÉ?
DM. In SENSIBILITÉ, my focus lies at the intersection of information theory and computation, in order to understand how we can use communication networks for computational purposes.
In the past, we have been using communication networks, transmitting raw data from one party to another or from multiple sources of data to one or many destinations. However, instead of the typical approach, we can exploit the structures of sources, functions, and networks to reduce the transmission load. This can be realized by finding suitable functional representations of the sources and the computational tasks. In other words, we want to understand “what is the minimum possible amount of bits that we need for the computations and transmissions to be able to achieve a desired computation task over a network, given that the sources are distributed, meaning that they can’t talk to each other?” Equivalently, the goal is to recover a function of distributed data rather than recovering the data in its entirety.
Here, we have to note that, in practice, computational tasks exhibit high nonlinearity and therefore, might not have interpretable functional representations. The challenge is to break down a task into multiple parts over a network with physical constraints and unravel how to distribute parts of the computation at different network nodes.
Q. Could you refer to a practical scenario for better understanding what computation over a network is?
DM. Let us consider a scenario where a distributed network of sensors collects the local temperature information, which is highly-correlated. Now, this information needs to be sent over the network to a common destination. The objective of the destination is to compute whether the average temperature exceeds a certain threshold. Exploiting the highly correlated nature of data, we can reduce the transmission volume by exploiting the joint data distribution, saving the transmissions.
This type of work has been studied in the context of distributed source coding. However, we incorporate the aspects of functions and networks. For most networks, the rate region of communication is an open problem. Hence, determining the rate region to compute general functions over general network scenarios is an open and challenging problem.
That is why I attempt to study this problem by considering tractable network scenarios first and functions for which the decomposition is doable. After getting a solid hold of small-scale models, I will move to more general settings with higher complexity in terms of function and network structures.
Q. It seems an ambitious task for a 5-year grant. What are the limitations and challenges you see ahead?
DM. SENSIBILITÉ indeed has challenges. A primary one deals with the decomposition of nonlinear functions. Even when the theoretical decomposition is possible, it might not be feasible to implement nonlinear functions over networks. This is because the physical constraints imposed by a network might not permit an arbitrary decomposition over the network; this is a big challenge. To that end, I believe that we can benefit from approximation theory since our goal in some instances is to have partial recovery of the functions (with losses) versus the exact representations over networks. In addition, we need to develop low-complexity algorithms for the implementation. Devising practical solutions could be very challenging since the problem of computation over communication networks relies on concepts from graph theory. The existing compression algorithms rely on graph colorings (NP-complete problems), implying an increased complexity with the scale of the problem. I am motivated to be able to deal with scenarios where polynomial complexity algorithms are handy.
These two are the main risks, with the possibility of more. Over the 5-year period, I hope to have solid results, along with my future team of students, postdocs, and engineers.
Q. What are the real-life applications of this project?
DM. This project is mainly on the theoretical side of the fundamental aspects of information theory and communication networks, with a couple of practical application scenarios that we consider to validate our theory.
The first one is IoT devices for federated learning scenarios. There can be a benefit of using communication networks in these scenarios, where one can harness the interference of the network and facilitate the computation. Another edge-computing application we consider is content caching for computation, which can also be posed as a non-linear computational problem with side information.
Also, distributed source compression ideas can be generalized to distributed functional compression, especially with high dimensional data. For example, in computational imaging it is crucial to detect patterns in data, and massive data compression for huge data volumes is desired. In analogy, what I am trying to understand is the patterns in the source distributions and functions in order to be able to minimize the cost of computation.
Another application is holographic communications, which cannot tolerate delays, so there is a need to design protocols that support this requirement of achieving real-time zero-error computing.
Q. What are the next steps and the desired impact of the SENSIBILITÉ project?
DM. At the end of the 5-year grant, I would like to see significant gains in computational and communication complexity by providing parsimonious representations for the computation tasks. This is the holy grail of the project.
We want to achieve a significant reduction in the complexity of the communication and be able to represent it using analytical formulas, with tools from information and graph theory, as well as new tools that we will discover during the project.
From the most practical aspect, we would like to achieve a large-scale computation at a low cost in order to be able to scale to large networks.
What I envision for the future is to bring down the complexity using the structural information of the source, the function, and the network. In addition, to determine which functions can be efficiently computed over a given network and vice versa.
I would like to start building my team soon, so I will be recruiting students and postdocs to work on SENSIBILITÉ around spring 2023. It is critical to find good students, so if you have a solid mathematical background and an aptitude for conducting research at the intersection of information theory and computation problems, do not hesitate to contact me!