Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast
Abstract
This work studies non-linear function computation broadcast (NFCB), in which a sender with access to N datasets (X1,…,XN) 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 Xi 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.
Related
- Cache-Aided Linear Function Computation
- Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels
- Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
- A Graph-Theoretic Approach to Matrix AM-GM: Counterexamples and Sharp Exponential Bounds
- Yau's number-theoretic conjecture and sharp spectral bounds for quantum harmonic oscillators
BibTeX
@misc{malak2026graphtheoretic,
title = {{Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast}},
author = {Derya Malak and Vijith Kumar K. P. and M. Reza Deylam Salehi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08202},
eprint = {2610.08202},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08202},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast
AU - Derya Malak
AU - Vijith Kumar K. P.
AU - M. Reza Deylam Salehi
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08202
UR - https://arxiv.org/abs/2610.08202
AB - This work studies non-linear function computation broadcast (NFCB), in which a sender with access to N datasets (X_1,…,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.
ER -