Metraipolis › archive › dc_67fbd503fde0

Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio — arXiv:2610.42023

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.42023
License (as archived)
CC0-1.0
Archived
2026-11-02T05:01:34.041Z
SHA-256 of the archived text
0f95299c5fa25cd14a901a2f7b3509c23046548a376d6a9afa81ffb799041ac0
Stable URL of this page
https://metraipolis.com/documento/dc_67fbd503fde0

How to cite

Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio — arXiv:2610.42023 — arXiv (en), https://arxiv.org/abs/2610.42023 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_67fbd503fde0 (Metraipolis archive dc_67fbd503fde0, sha256 0f95299c5fa25cd14a901a2f7b3509c23046548a376d6a9afa81ffb799041ac0)
BibTeX
@misc{dc67fbd503fde0,
  title = {Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio — arXiv:2610.42023},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42023},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_67fbd503fde0; sha256 0f95299c5fa25cd14a901a2f7b3509c23046548a376d6a9afa81ffb799041ac0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42023. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

$K$ users each observe a fixed linear function of common data over a finite field of characteristic $p$, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe $\boldsymbol{a}$, $\boldsymbol{b}$ and $\boldsymbol{a}+\boldsymbol{b}$ and the server wants $\boldsymbol{a}+\lambda\boldsymbol{b}$. The four functions span four lines in a plane with cross-ratio $\lambda$, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every $\lambda$, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, $\lambda=-1$, $\lambda=2$ or $2\lambda=1$, it is $2$: every zero-error code reveals $(\boldsymbol{a},\boldsymbol{b})$ to the server, so no code beats having two users send their observations. For $\lambda$ outside the prime subfield it is the cut-set bound $3/2$, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other $\lambda$ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for $\lambda$ outside the prime subfield. The four-line instance is also exact repair of one node of a $[4,2]$ MDS storage code, and the results translate to that setting.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.42023 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:48:12.640Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).