Non-Linear Function Computation Broadcast
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917929175482368 |
|---|---|
| author | Salehi, Mohammad Reza Deylam Purakkal, Vijith Kumar Kizhakke Malak, Derya |
| author_facet | Salehi, Mohammad Reza Deylam Purakkal, Vijith Kumar Kizhakke Malak, Derya |
| contents | This work addresses the $K$-user computation broadcast problem consisting of a master node, that holds all datasets and users for a general class of function demands, including linear and non-linear functions, over finite fields. The master node sends a broadcast message to enable each of $K$ distributed users to compute its demanded function in an asymptotically lossless manner with user's side information. We derive bounds on the optimal $K$-user computation broadcast rate that allows the users to compute their demanded functions by capturing the structures of the computations and available side information. Our achievability scheme involves the design of a novel graph-based coding model to build a broadcast message to meet each user's demand, by leveraging the structural dependencies among the datasets, the user demands, and the side information of each user, drawing on K{ö}rner's characteristic graph framework. The converse uses the structures of the demands and the side information available at $K$ users to yield a tight lower bound on the broadcast rate. With the help of examples, we demonstrate our scheme achieves a better communication rate than the existing state of the art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13688 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Non-Linear Function Computation Broadcast Salehi, Mohammad Reza Deylam Purakkal, Vijith Kumar Kizhakke Malak, Derya Information Theory This work addresses the $K$-user computation broadcast problem consisting of a master node, that holds all datasets and users for a general class of function demands, including linear and non-linear functions, over finite fields. The master node sends a broadcast message to enable each of $K$ distributed users to compute its demanded function in an asymptotically lossless manner with user's side information. We derive bounds on the optimal $K$-user computation broadcast rate that allows the users to compute their demanded functions by capturing the structures of the computations and available side information. Our achievability scheme involves the design of a novel graph-based coding model to build a broadcast message to meet each user's demand, by leveraging the structural dependencies among the datasets, the user demands, and the side information of each user, drawing on K{ö}rner's characteristic graph framework. The converse uses the structures of the demands and the side information available at $K$ users to yield a tight lower bound on the broadcast rate. With the help of examples, we demonstrate our scheme achieves a better communication rate than the existing state of the art. |
| title | Non-Linear Function Computation Broadcast |
| topic | Information Theory |
| url | https://arxiv.org/abs/2502.13688 |