arXiv preprint ·
On the optimality of truncation among binary linear sketches
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Proper Agnostic Learning of Halfspaces
Semidirect sums of tensors and the matrix multiplication exponent
State Synthesis with an NP oracle
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.