Distributed Compression for Computation and Bounds on the Optimal Rate
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_ | 1866909588464336896 |
|---|---|
| author | Salehi, Mohammad Reza Deylam Malak, Derya |
| author_facet | Salehi, Mohammad Reza Deylam Malak, Derya |
| contents | We address the problem of distributed computation of arbitrary functions of two correlated sources $X_1$ and $X_2$, residing in two distributed source nodes, respectively. We exploit the structure of a computation task by coding source characteristic graphs (and multiple instances using the $n$-fold OR product of this graph with itself). For regular graphs and general graphs, we establish bounds on the optimal rate -- characterized by the chromatic entropy for the $n$-fold graph products -- that allows a receiver for asymptotically lossless computation of arbitrary functions over finite fields. For the special class of cycle graphs (i.e., $2$-regular graphs), we establish an exact characterization of chromatic numbers and derive bounds on the required rates. Next, focusing on the more general class of $d$-regular graphs, we establish connections between $d$-regular graphs and expansion rates for $n$-fold graph powers using graph spectra. Finally, for general graphs, we leverage the Gershgorin Circle Theorem (GCT) to provide a characterization of the spectra, which allows us to build new bounds on the optimal rate. Our codes leverage the spectra of the computation and provide a graph expansion-based characterization to efficiently/succinctly capture the computation structure, providing new insights into the problem of distributed computation of arbitrary functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15706 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Compression for Computation and Bounds on the Optimal Rate Salehi, Mohammad Reza Deylam Malak, Derya Information Theory We address the problem of distributed computation of arbitrary functions of two correlated sources $X_1$ and $X_2$, residing in two distributed source nodes, respectively. We exploit the structure of a computation task by coding source characteristic graphs (and multiple instances using the $n$-fold OR product of this graph with itself). For regular graphs and general graphs, we establish bounds on the optimal rate -- characterized by the chromatic entropy for the $n$-fold graph products -- that allows a receiver for asymptotically lossless computation of arbitrary functions over finite fields. For the special class of cycle graphs (i.e., $2$-regular graphs), we establish an exact characterization of chromatic numbers and derive bounds on the required rates. Next, focusing on the more general class of $d$-regular graphs, we establish connections between $d$-regular graphs and expansion rates for $n$-fold graph powers using graph spectra. Finally, for general graphs, we leverage the Gershgorin Circle Theorem (GCT) to provide a characterization of the spectra, which allows us to build new bounds on the optimal rate. Our codes leverage the spectra of the computation and provide a graph expansion-based characterization to efficiently/succinctly capture the computation structure, providing new insights into the problem of distributed computation of arbitrary functions. |
| title | Distributed Compression for Computation and Bounds on the Optimal Rate |
| topic | Information Theory |
| url | https://arxiv.org/abs/2504.15706 |