This talk presents the main results of my PhD thesis, defended in 2024 at Sorbonne University, devoted to the theoretical study of multi-user distributed computation for linearly-decomposable functions. In this framework, we construct a general model in which a matrix of computational demands can be factorized into two sparse matrices—a computation matrix and a communication matrix—revealing deep connections with several areas: coding theory, covering codes, syndrome decoding, compressed sensing, and fixed-support matrix factorization (tessellation).
We will discuss:
- fundamental lower and upper bounds on computation and communication costs;
- the characterization of a new class of codes, called partial covering codes;
- optimal architectures for perfect distributed computing;
- a new method called Tessellated Distributed Computing, offering optimal computation–communication trade-offs, both in the exact and approximate regimes.
These results lead to practical applications in large-scale distributed systems, distributed machine learning, and high-performance computing infrastructures.
Bio: Ali Khalesi is an Assistant Professor (Maître de conférences) at IPSA, Ivry-sur-Seine, and recipient of the 2nd Prize for the Best PhD Thesis—EDITE Paris 2025, as well as finalist for the 2025 Chancellerie de Paris Awards.
He obtained his PhD in 2024 from Sorbonne University, within EURECOM, under the supervision of Prof. Petros Elia.
His research focuses on the fundamental limits of distributed computing, information theory, coding theory, and the analysis of communication–computation trade-offs in modern distributed architectures.