On the optimality of truncation among binary linear sketches
Abstract
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 Θ(n log n) bits to achieve constant error, while a nonlinear protocol only requires O(log n) bits.
Related
- Symmetric Hermite quadrature-based balanced truncation for learning linear dynamical systems from derivative data
- The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample
- Optimality of Affine Policies in Distributionally Robust Linear-Quadratic Control with Temporally Correlated Noise
- A Behavioral approach to Constrained Linear Quadratic Control: Feasibility and Optimality
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
BibTeX
@misc{cung2026optimality,
title = {{On the optimality of truncation among binary linear sketches}},
author = {Robinson D. H. Cung and Adway Girish and Emre Telatar},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03979},
eprint = {2611.03979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03979},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the optimality of truncation among binary linear sketches
AU - Robinson D. H. Cung
AU - Adway Girish
AU - Emre Telatar
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03979
UR - https://arxiv.org/abs/2611.03979
AB - 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 Θ(n log n) bits to achieve constant error, while a nonlinear protocol only requires O(log n) bits.
ER -