Distributed Approximate Computing with Constant Locality
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913247466094592 |
|---|---|
| author | Yuan, Deheng Guo, Tao Huang, Zhongyi Jin, Shi |
| author_facet | Yuan, Deheng Guo, Tao Huang, Zhongyi Jin, Shi |
| contents | Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only constant number of compressed bits. We establish an achievable rate region by designing an efficient layered coding scheme, where the coding rate is reduced by introducing auxiliary random variables and local decoding is achieved by exploiting the expander graph code. Then we show the rate region is optimal under mild regularity conditions on source distributions. The proof relies on the reverse hypercontractivity and a rounding technique to construct auxiliary random variables. The rate region is strictly smaller than that for the classical problem without the constant locality constraint in most cases, which indicates that more rate is required in order to achieve lower coding complexity. Moreover, a coding for computing problem with side information is analogously studied. We also develop graph characterizations, which simplifies the computation of the achievable rate region. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04141 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Distributed Approximate Computing with Constant Locality Yuan, Deheng Guo, Tao Huang, Zhongyi Jin, Shi Information Theory Consider a distributed coding for computing problem with constant decoding locality, i.e., with a vanishing error probability, any single sample of the function can be approximately recovered by probing only constant number of compressed bits. We establish an achievable rate region by designing an efficient layered coding scheme, where the coding rate is reduced by introducing auxiliary random variables and local decoding is achieved by exploiting the expander graph code. Then we show the rate region is optimal under mild regularity conditions on source distributions. The proof relies on the reverse hypercontractivity and a rounding technique to construct auxiliary random variables. The rate region is strictly smaller than that for the classical problem without the constant locality constraint in most cases, which indicates that more rate is required in order to achieve lower coding complexity. Moreover, a coding for computing problem with side information is analogously studied. We also develop graph characterizations, which simplifies the computation of the achievable rate region. |
| title | Distributed Approximate Computing with Constant Locality |
| topic | Information Theory |
| url | https://arxiv.org/abs/2312.04141 |