Metraipolis › archive › dc_257d8448cfed

On the optimality of truncation among binary linear sketches — arXiv:2611.03979

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03979
License (as archived)
CC0-1.0
Archived
2026-11-04T19:01:54.911Z
SHA-256 of the archived text
2927601119a26971c2837bed3ded5b977bcdbe649142c3b279079b22d453b205
Stable URL of this page
https://metraipolis.com/documento/dc_257d8448cfed

How to cite

On the optimality of truncation among binary linear sketches — arXiv:2611.03979 — arXiv (en), https://arxiv.org/abs/2611.03979 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_257d8448cfed (Metraipolis archive dc_257d8448cfed, sha256 2927601119a26971c2837bed3ded5b977bcdbe649142c3b279079b22d453b205)
BibTeX
@misc{dc257d8448cfed,
  title = {On the optimality of truncation among binary linear sketches — arXiv:2611.03979},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03979},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_257d8448cfed; sha256 2927601119a26971c2837bed3ded5b977bcdbe649142c3b279079b22d453b205},
  year = {2026}
}

Archived text

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

We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements. We show that under a certain monotonicity condition, simply truncating the input by retaining a subset of its coordinates is optimal among all linear sketches of the same size. In particular, this applies to distributed testing of correlations of binary vectors when they are of opposite signs and evaluating unate Boolean functions on uniformly random inputs. Additionally, given that truncation is optimal, we immediately have lower bounds for arbitrary binary linear sketches. To illustrate this application, we consider the one-way communication complexity of a distributional graph connectivity problem on $n$ vertices and show that truncation, and hence all binary linear sketches, requires $\Theta(n \log n)$ bits to achieve constant error, while a nonlinear protocol only requires $O(\log n)$ bits.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2611.03979 — 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-04T18:38:39.767Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).