On the optimality of truncation among binary linear sketches
cs.DS, cs.CC, cs.IT, math.IT
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 20 pages. Submitted to STOC 2027
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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 n) bits to achieve constant error, while a nonlinear protocol only requires O(n) bits.
Sources
- On The Most Discriminative Boolean Functions for Correlated Sources
- On Binary Distributed Hypothesis Testing
- The "Most informative boolean function" conjecture holds for high noise
- The Condition for Structured Coding to Improve Random Coding in the Binary Modulo-sum Problem
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time