Summary
This paper looks at how to send information efficiently when a sender holds multiple datasets and wants to broadcast specific computed results to multiple users, each having some related knowledge. The authors use graph theory to model the problem, capturing various sources and demands in a new way. They develop new techniques to find the lowest possible communication rate under general conditions and prove new limits for these scenarios. Their results show that using non-linear methods can sometimes outperform traditional linear methods in sending these computations. The work helps understand the best ways to compress and broadcast computed data when users have different side information and needs.
What this means in practice
- •For network protocol engineers: Design broadcast protocols that minimize communication when sending computed results to devices with partial knowledge using non-linear coding schemes.
- •For distributed storage developers: Optimize data retrieval in distributed storage systems by efficiently broadcasting computed functions to clients with cached side information.
A theory result. No direct application yet.
Abstract
This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.