Hierarchical Gradient Coding
November 29, 2025
The Gradient Coding problem referes to the setting where the computation of gradient is outsourced to multiple workers. Since not every worker would be reliable, to ensure the robustness of the system,
the scheme should be designed to tolerate some straggling workers; either because of a broken link or slow computation. We extended the setting to hierarchical gradient coding, where we consider intermediate nodes referred to as relays between the server and the workers. We then characterized the optimal communication-computation trade-off for all the links in the system through designing
universal encoding polynomials.
We then added the private hierarchical setting where we keep the gradient information of any subset of the data private to the relays, such that the final gradient could still be computed at the server.
A short version of our results was accepted and presented at ISIT 2025 (Optimal Communication-Computation Trade-off in Hierarchical Gradient Coding), and the complete version is available on arXiv (Hierarchical Gradient Coding: From Optimal
Design to Privacy at Intermediate Nodes), which is submitted to IEEE Transactions on Information Theory.
Multi-Message Private Computation
November 28, 2025
In the private information retreival (PIR) setting, the goal is that the user retreives a filen by sending queries to multiple servers, each storing the same library, and receiving corresponding answers from each server, while keeping the demanded file index private to each server. This is only possible if no matter the choice of demanded file, the distribution on the query sent to each server, remains the same. This becomes more challenging, when the aim is to reach the minimum amount of download needed from each server, a parameter referred to as the capacity.
The multi-message private computation (MM-PC) setting extends the PIR setting to the case where the user is allowed to request multiple (instead of one) linear combinations (instead of files themselves) of the files in the library. To that end, we have designed symmetric queries sent to the servers, where each request a linear combination of subpackets of possibly multiple files. We then show that some of these queries would be redundant (using the fact that the requests of the user are in the end linear combinations of some limited independent files), which helps to reduce the amount of download through an MDS-coded masking. We show that the resulted schemes would be order-optimal in most parameter regimes. As a by-product, the designed scheme leads to a new capacity-achieving private computation scheme for the case of one linear request.
A short version of our results was accepted and presented at ISIT 2024 (On Multi-Message Private Computation), and the complete version is published on IEEE Transaction on Communications (Fundamental Limits of Multi-Message Private Computation).
Private Coded Caching
November 27, 2025
In this project, we investigated the private coded caching scenario, where the aim is to preserve the demand privacy for all the users in the system. Specifically, our aim was to extend the
privacy garauntee to a multi-delivery scenario, in which there are multi rounds of delivery for multi rounds of demand vectors with a single cache phase in the beginning. To that end, we introduced
a new private caching setting, in which not only the demand information should be kept private, but also the cache information, for a single round of delivery.
The product of this work unweiled an interesting connection between coded cachinhg and private information retrieval (PIR) settings. The core idea lies in the fact that
the cache content of a user and the multicast messages in the delivery phase could be resembled as the message of two servers in a two-server PIR scheme.
This connection opens the gate between coded caching and PIR which leads to order-optimal schemes for private caching settings. A short version of the results was accepted and presented at ISIT 2022 (Coded Caching With Private Demands and Caches) and the complete version was published on IEEE Transactions on Information Theory (Coded Caching With Private Demands and Caches).