ERC PROJECT SENSIBILITÉ (2023-2028)

 Computing Nonlinear Functions over Communication Networks

SENSIBILITÉ describes a novel theory for distributed computing of nonlinear functions over communication networks. Motivated by the long-lasting open challenge to invent technologies that scale with the network size, this intriguing and far-reaching theory elevates distributed encoding and joint decoding of information sources, to the critical network computing problem for a class of network topologies and a class of nonlinear functions of dependent sources. Our theory will elevate distributed communication to the realm of distributed computation of any function over any network. 

Our research focuses on distributed computation, in the presence of structured and correlated data, and in the presence of limited network capacity. This captures a variety of distributed computing and distributed learning scenarios of interest. My approach aims to fuse a computer science-inspired view of distributed computing with the rigorous machinery of information theory, and the clever design stemming from coding theory.

Our SENSIBILITÉ team has used some of the most recent and, in many ways, subtle results in information theory to devise a theoretically motivated look at the central problem of coordinating computation and caching in networks. Most recently, we have been researching in the direction of distributed compression of information for computing functions over communication networks, exploiting graph theory and function representations in computer science, as well as coding and information theory, toward a novel perspective on the fundamental underpinnings of computation and communications in networks. This research paves the way for unraveling the tradeoffs between communication rate and computation cost.

CONTRIBUTIONS

Our major research contributions in the context of SENSIBILITÉ include the following:

1. K. K. K. Namboodiri, E. Peter, D. Malak, and P. Elia, ``Fundamental Limits of Distributed Computing for Linearly Separable Functions", arXiv preprint, Sep. 2025.

This work addresses the problem of distributed computation of linearly separable functions, where a master node with access to K datasets, employs N servers to compute L user-requested functions, each defined over the datasets. Servers are instructed to compute subfunctions of the datasets and must communicate computed outputs to the user, who reconstructs the requested outputs. The central challenge is to reduce the per-server computational load and the communication cost from servers to the user, while ensuring recovery for any possible set of L demanded functions. 

We here establish the fundamental communication–computation tradeoffs for arbitrary K and L, through novel task-assignment and communication strategies that, under the linear-encoding and nosubpacketization assumptions, are proven to be either exactly optimal or within a factor of three from the optimum. In contrast to prior approaches that relied on fixed assignments of tasks – either disjoint or cyclic assignments – our key innovation is a nullspace-based design that jointly governs task assignment and server transmissions, ensuring exact decodability for all demands, and attaining optimality over all assignment and delivery methods. To prove this optimality, we here uncover a duality between nullspaces and sparse matrix factorizations, enabling us to recast the distributed computing problem as an equivalent factorization task and derive a sharp information-theoretic converse bound. Building on this, we establish an additional converse that, for the first time, links the communication cost to the covering number from the theory of general covering designs. 

2. D. Malak, ``Structured Codes for Distributed Matrix Multiplication," arXiv preprint, Dec. 2024. 

In the first part of this work, we develop encoding schemes for distributed source compression tailored to nonlinear transformations, including inner products, symmetric matrix products, and general square matrix products over finite fields. Our approach combines nonlinear mappings of distributed sources A and B with the structured linear encoding scheme by Körner and Marton, ensuring distributed computation without requiring full data disclosure. 

We derive achievable and converse bounds on the sum rate for distributed computation of inner products <A, B> and general matrix products A'B, accommodating non-commutative or asymmetric source matrices. We leverage the scheme of Körner-Marton that captures the structure of matrix computation, and demonstrate that the following sum rate is achievable:

We demonstrate unbounded compression gains over Slepian-Wolf coding (with a communication cost given by H(A , B)) in cases with specific source correlations, validated by analytical and simulation-based evidence, conditions for rate savings with less stringent correlation structures, and when the sum rate can drop below twice the entropy (given by 2H(A'B)) of the target computation. Furthermore, we upper bound the multiplicative gaps from the lower bounds on the communication cost set by Han-Kobayashi (given by H(A | B)+H(B | A)). 

In the second part, we introduce a new class of polynomial codes ---structured polynomial codes (StPolyDot codes) --- designed for distributed matrix multiplication in a master-workers-receiver framework. We analyze storage costs for workers alongside end-to-end communication and computation costs, and extend StPolyDot codes to support both chain matrix multiplications and information-theoretically secure computations. Our results show that, by leveraging Körner-Marton's distributed scheme, StPolyDot codes retain the optimality of the communication cost of Dutta et al.'s approach within a factor of 2. Notably, StPolyDot codes achieve this even for distributed master nodes with only a bounded increase in computation cost, inversely proportional to the memory parameter.   

3. D. Malak, M. R. Deylam Salehi, B. Serbetci, P. Elia, ``Multi-Server Multi-Function Distributed Computation," ENTROPY (Special issue: ``Foundations of Goal-Oriented Semantic Communication in Intelligent Networks"), vol. 26, no. 6, p. 448, Jun. 2024. 

The work here studies the communication cost for a multi-server multi-task distributed computation framework, and does so for a broad class of functions and data statistics. Considering the framework where a user seeks the computation of multiple complex (conceivably non-linear) tasks from a set of distributed servers, we establish communication cost upper bounds for a variety of data statistics, function classes and data placements across the servers.    

To do so, we proceed to apply, for the first time here, Körner's characteristic graph approach --- which is known to capture the structural properties of data and functions --- to the promising framework of multi-server multi-task distributed computing. Going beyond the general expressions, and in order to offer clearer insight, we also consider the well-known scenario of cyclic dataset placement and linearly separable functions over the binary field, in which case our approach exhibits considerable gains over the state of art. Similar gains are identified for the case of multi-linear functions.

NEWS

• PEPR Interview

• I am honored to be awarded the ERC Starting Grant for my project SENSIBILITÉ at the intersection of computation and information theory (read our blog). 

• Recipient of the European Research Council (ERC) 2022 Starting Grant on a research proposal titled, ``Computing Nonlinear Functions over Communication Networks (SENSIBILITÉ)", 2023-2028.