Limites Fondamentales du calcul distribué de fonctions non-linéaires dans certains réseaux multi-utilisateurs

In the era of massive data generation and complex distributed systems, handling the computation costs over networks has become a central challenge. As modern applications in cloud computing, machine learning, and data analytics shift toward distributed architectures, the focus has moved from traditional source coding to functional compression—computing functions of data rather than recovering the data itself. This thesis develops achievable schemes for distributed function computation over communication networks. Using characteristic graphs, which capture the structural dependencies between data sources and functions, we optimize communication costs across three settings: Graph-Theoretic Limits of Distributed Computation: We study the distributed computation of arbitrary functions over correlated sources using characteristic graphs and their n-fold OR products. Our framework derives rate bounds based on chromatic entropy for cyclic, d-regular, and general graphs. For cycle graphs, we establish exact results, while for d-regular and general graphs, we develop new bounds on their graph entropies by leveraging spectral properties, including regions that approximate the eigenvalues of the characteristic graph adjacency matrix. These results reveal how the graph structure and spectrum relate to compressibility and communication efficiency. Multi-Server Multi-Function Distributed Computation: Extending the characteristic graph framework to multi-server, multi-function settings, we analyze scenarios where a user requests complex functions from distributed servers. Our achievability bounds capture the interplay between function structure, source correlations, and data placement. For linearly and non-linearly separable functions, under cyclic placement, our schemes significantly reduce communication costs compared to existing methods, offering new insights into distributed task allocation and network-aware computation. Non-Linear Function Computation Broadcast: We study a broadcast model in which a central node (master) enables K users to compute distinct, potentially non-linear functions using their individual side information. Leveraging a novel graph-based coding scheme, we capture the structural dependencies among datasets, user demands, and side information. We derive tight achievability and converse bounds that generalize classical results on the K-user linear computation broadcast and the 2-user non-linear computation broadcast problems, and show strict improvements over the existing schemes, using characteristic graphs and variable length coding. For example, we demonstrate lower rates versus the K-user linear computation broadcast problem. This thesis leverages graph-theoretic tools for distributed source and distributed functional compression, offering rigorous foundations and practical schemes for computation over networks. The organization of this dissertation is as follows. Chapter 1 introduces the distributed computation frameworks addressed in this work and outlines our contributions. Chapter 2 develops a graph-theoretic approach for functional compression. Chapter 3 applies the characteristic graph framework to a multi-function, multi-server setting. Chapter 4, leveraging characteristic graphs, explores the fundamental limits of broadcast function computation. Finally, Chapter 5 concludes the results presented in this dissertation and details the key future directions.