Metraipolis › archive › dc_bfbf52ca5a6e

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-02T08:01:41.328Z
SHA-256 of the archived text: 2d36a983e70835d42d6ddcacdd10b93bda4dbfa18539077c9d404375210763df
Stable URL of this page: https://metraipolis.com/documento/dc_bfbf52ca5a6e

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_bfbf52ca5a6e (Metraipolis archive dc_bfbf52ca5a6e, sha256 2d36a983e70835d42d6ddcacdd10b93bda4dbfa18539077c9d404375210763df)

BibTeX

@misc{dcbfbf52ca5a6e,
  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_bfbf52ca5a6e; sha256 2d36a983e70835d42d6ddcacdd10b93bda4dbfa18539077c9d404375210763df},
  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-02T07:43:00.684Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).