On the optimality of truncation among binary linear sketches

Introduction

Linear sketches are a fundamental algorithmic tool to process high-dimensional data, particularly when dealing with space and communication constraints [8, 46, 59]. A linear sketch represents a vector $x$ of dimension $n$ by a vector $Ax$ (of dimension $k \le n$), the product of $x$ with a $k \times n$ matrix $A$. Being linear, the (linear) sketch of $x+y$ can be easily obtained by summing the sketches of $x$ and $y$. This makes them particularly attractive in communication problems as they allow sketches of distributed observations to be easily aggregated [CG05; ACH+13; AGM12a; AGM12b], and in streaming problems, where the sketch of a changing input can be efficiently updated [34, 46, 22].

In this paper, we focus on linear sketches over $\mathbb{F}_2$ (which we call binary linear sketches; the words “binary” and “linear” may be dropped when clear from context), as studied by [37]. Formally, a binary linear sketch of $x \in\mathbb{F}_2^n$ is the product $Ax$ where the matrix $A$ has entries in $\mathbb{F}_2$ and matrix multiplication is performed over $\mathbb{F}_2$. Hence, a $k$-bit linear sketch consists of $k$ parity measurements on the vector $x$. The restriction to $\mathbb{F}_2$ is not as limiting as it might first appear. Indeed, Kannan, Mossel, Sanyal, and Yaroslavtsev [37] explicitly write that they are “unaware of any problem for which sketching over reals gives any advantage over $\mathbb{F}_2$”, and note that all (then) known dynamic graph streaming algorithms (except [35]) can be seen as binary linear sketches without losing space-optimality. Despite their simple structure, binary linear sketches capture the power of general streaming algorithms in several settings [32], in addition to being studied in their own right for hashing and randomness extraction [16, 4, 18].

We consider using such sketches for downstream statistical inference and function evaluation tasks. Among all $k$-bit linear sketches, the simplest choice is to retain $k$ of the $n$ input coordinates, which we call truncation. We ask the following general question:

When is a simple truncation of the input the best binary linear sketch?

By input we refer to the observations that the statistical inference is based on, or the evaluation point of the function, as the case may be. We give a monotonicity condition that guarantees the optimality of truncation, and provide applications to distributed correlation testing and Boolean function evaluation. Lower bounds on truncation then also hold for all linear sketches; we use this to establish the strict suboptimality of linear sketches against nonlinear encoders in a distributional graph connectivity problem with one-way communication.

Linear maps are classical tools in coding theory [51, 25] and compressed sensing [19], where the goal is to recover the entire input. They are also useful to recover a function of the input: Körner and Marton [36] showed that applying the same binary linear sketch to two symmetrically correlated binary vectors is optimal for recovering their modulo-2 sum; see [57] for recent developments. Since the modulo-2 sum is a sufficient statistic for a hypothesis test on the correlation, one might expect linear sketches to also perform well for statistical inference problems involving correlation. Indeed, linear sketches are known to improve upon classical random quantization for distributed hypothesis testing between certain pairs of positive correlations [28, 29].

In our previous work [23], however, we showed that when the correlations have equal magnitude and opposite signs, or when either correlation is zero, no binary linear sketch can do better than trivially retaining the same subset of coordinates (and the latter is easily shown to be worse than classical quantization, hence linear sketches are strictly suboptimal for this problem). We conjectured that truncation remains optimal among binary linear sketches for every pair of correlations of opposite signs (and possibly different magnitudes). In the present paper, we resolve this conjecture in the affirmative.

This optimality of simple coordinate projections is reminiscent of the Courtade–Kumar conjecture [14], with a long line of works (e.g., [53, 49, 20]) over the last decade culminating in three independent proofs earlier this year [CGJ+26; KT26; MB26]. It states that dictator functions are the “most informative”, i.e., among all functions mapping a uniform vector $X$ to a single bit, truncation (to a single coordinate) has the highest mutual information with a version of $X$ that has each coordinate flipped independently with a fixed probability. We study an analogous question for a more general decision-theoretic notion of optimality (Blackwell dominance [10]) and arbitrary sketch dimension $k$, but restricted to the class of binary linear sketches.

A more closely related analogue is lossy compression using binary linear sketches. Ancheta [9] showed that among such sketches, truncation is optimal (achieving minimum asymptotic expected reconstruction Hamming distance) for uniformly random binary vectors (see also [43]). They conjectured that for biased binary vectors, the optimal linear sketch is truncation followed by lossless compression of the retained coordinates; this was also resolved positively earlier this year [60].

Before describing our results, it is worth clarifying the following: Much of the sketching literature chooses the matrix $A$ at random. We consider deterministic matrices as in, e.g., [47, 42, 37]. Choosing a random matrix can improve worst-case guarantees, but for a given input distribution and an “average-error” performance metric, some fixed matrix performs at least as well as any randomized choice [38]. Our results hold for every fixed matrix and extend to settings where the sketches are chosen via shared randomness that is independent of the input.

Results

We show that truncation is the optimal binary linear sketch for the following two problems: distributed testing of correlations between binary vectors observed at different terminals using sketches, and evaluating unate Boolean functions from sketches (resp. (i) and (ii) in the list below). Beyond identifying the conceptually simplest scheme to be optimal, this provides a method to establish the limitations of binary linear sketches. In general, linear sketches can involve parities of large, overlapping sets, whose analysis can be non-trivial and require specialized machinery (e.g., using approximate Fourier dimensions [37]). We illustrate the ease with which truncation yields lower bounds on all such linear sketches using a toy graph connectivity testing problem (iii) below). More precisely, we show the following.

(i) Distributed correlation testing. In § 3, we consider the distributed correlation testing setting of [28, 23]. Alice and Bob observe the respective components of $n$ independent binary pairs with uniform marginals and correlation $\rho_h$ under hypothesis $h \in\{0,1\}$. They send $k_A$ and $k_B$ binary linear measurements respectively to a central tester. When the correlations are of opposite signs, i.e., $\rho_0\rho_1 \le0$, we show (Theorem 1) that simply sending the same $k = \min\{k_A,k_B\}$ coordinates at both agents achieves the optimal type-I–type-II error trade-off among all binary linear encoders. This proves the opposite-correlation conjecture from [23].

(ii) Evaluating unate functions from linear sketches. A Boolean function is unate if it can be made coordinate-wise non-decreasing by flipping a fixed subset of its input coordinates. For a uniformly random binary input vector, we show in Theorem 2 that truncation (to an appropriate set of $k$ coordinates) is the best choice for evaluating the function at the vector from $k$ binary linear measurements of it. That is, for any rank-$k$ matrix $A$, the best estimate of $f(z)$ obtained from $Az$ is no better than the estimate obtained from the coordinates of $z$ indexed by $k$ linearly independent columns of $A$. See § 4 for more details.

(iii) Strict suboptimality of all linear sketches for graph connectivity. We consider the problem of one-way communication for graph connectivity [56] (see § 5 for background). Fix a graph. Alice observes a uniformly random subgraph $G$ of this graph and sends a message to Bob, who observes a fixed subgraph $H$ that is unknown to Alice. Bob must decide whether $G \cup H$ is connected with at most small constant error probability for every $H$. We take the original graph to be a complete bipartite graph with $v$ left and $2^v$ right vertices (and hence $n = v + 2^v$ total vertices) and show that arbitrary encoders can achieve this using $O(\log n)$ bits, while truncation (and hence all binary linear sketches) requires $\Theta(n \log n)$ bits (Theorem 3).

Technical overview

Our optimality proofs follow from the classical theory on comparing statistical experiments due to Blackwell [10, 11]. To show that truncation is optimal for a hypothesis test, we show that any binary linear sketch can be statistically simulated (as in (1)) from the truncated input through a transition kernel that does not depend on the hypothesis. Thus, any performance achieved by the sketch can also be achieved by truncation. The existence of such a kernel is characterized by data processing inequalities holding for all $f$-divergences (see § 2, Fact 1 for a formal statement).

Without loss of generality (w.l.o.g.), we can write any linear sketch of $x$ with a rank-$k$ matrix $A$ in the form $x_I \oplus\widetilde{A}x_{I^c}$, for some $I \subseteq[n] := \{1, \ldots, n\}$ and matrix $\widetilde{A}$ of appropriate dimension, where $x_I$ denotes the subvector of $x$ indexed by the elements of $I$ (by an invertible transformation applied to $Ax$). We compare $x_I$ against $x_I \oplus\widetilde{A}x_{I^c}$. In our most general technical result, we show that under an “opposite monotonicity” assumption on the joint distributions of the pair $(U,V)$ under the two hypotheses, $U$ on its own is better (via the $f$-divergence characterization) than the mixed statistic $U \oplus V$. The intuition is that under the opposite monotonicity assumption, mixing $V$ with $U$ weakens the evidence in favour of either hypothesis already present in $U$.

We first study the correlation testing problem (§ 3), where we consider sketches of the vector $X \oplus Y$, where $X$ and $Y$ are the correlated observations of Alice and Bob respectively with uniformly random marginals. It is easy to check that the opposite monotonicity assumption holds when the correlations are of opposite signs. However, we give a direct proof that exploits the coordinates of the vector being independent and identically distributed (i.i.d.), which reduces the problem to checking that a single bit of appropriate correlations can be simulated. This also gives an explicit kernel to show Blackwell dominance, as in the special cases considered in [23]. In fact, we prove the stronger statement that truncation cannot be improved by mixing any (possibly nonlinear) function of any quantity that is independent of the truncated coordinates (even if they carry useful information about the hypothesis).

As for the Boolean function evaluation setting (§ 4), we take the function value to be the “hypothesis” and unateness gives the desired opposite monotonicity. Finally, it is easy to check the graph connectivity predicate (§ 5) is indeed an unate function, and hence, truncation is the best linear sketch. We show that truncation (and hence any linear sketch) requires communication of at least a constant fraction of the number of edges, i.e., $\Theta(n \log n)$ bits to achieve small error, as a small fraction of edges can only account for a small fraction of the variance. On the other hand, we give a simple nonlinear scheme using the fact that most right vertices are non-isolated and that all remaining vertices form one connected component, which uses only $O(\log n)$ bits to achieve small constant error probability.

Open problems and future directions

The most cleanly stated open problem is to identify the exact set $\mathcal{R}_{k,n} \subseteq[-1,1]^2$ of correlation pairs $(\rho_0,\rho_1)$ for which truncation is the optimal linear sketch for finite $k,n$. We show here that $\rho_0\rho_1 \leq0$ is a sufficient condition for all $k \leq n$, but [23 Section 5] shows through numerical experiments that $R_{k,n}$ appears to shrink to the set of opposite-sign correlations as $k,n \to\infty$. Outside this region, does there exist such an optimal binary linear sketch, and can we identify it?

Further, what structural features of an inference problem allow for truncation to be the optimal sketch? We provide a sufficient monotonicity condition, but it would be interesting to characterize a more general property, e.g., through the Fourier structure of the conditional distributions. Such a characterization might prove useful in identifying other settings where truncation remains optimal.

More generally, can we identify how much communication is required to compensate for restrictions (such as linearity) on the encoder? For evaluating $f(X \oplus Y)$ at uniformly random $X$ and $Y$, [37] show that binary linear sketches can match the performance of arbitrary one-way encoders if they are allowed a constant-factor overhead in communication. Our comparison pits truncation against sketches of the exact same size without allowing for such overheads. It would be interesting to see if similar Blackwell comparisons can be obtained for other “simple” sketches that can match arbitrary encoders. Our graph connectivity example shows that the overhead factor can be $\Omega(n)$, so a constant factor does not suffice in general, but can we identify additional assumptions so that it does? This would help clarify when nonlinear encoders are essential, justifying their potentially greater implementation cost.

Preliminaries

We follow standard notation; a full summary is in Appendix § 10 for completeness.

Finally, our main technical tool is the notion of Blackwell dominance for comparing statistics: we take $U$ to be better than $V$ for testing between possible choices of the hypothesis $h$ if we can simulate $V$ from $U$ without knowing $h$. This has a clear interpretation: someone who observes $U$ can also simulate $V$ locally and make any decision that someone who observes only $V$ makes, and hence, cannot do worse. We also have a convenient characterization [10] of exactly when this partial order relation is satisfied, namely when all $f$-divergences satisfy a data processing inequality.

Distributed correlation testing

We study a communication game: Alice and Bob hold $X$ and $Y=X\oplus Z$ respectively, where $X$ is uniform on $\mathbb{F}_2^n$ and $Z$ has i.i.d. Bernoulli$(p_h)$ entries independent of $X$, under an unknown hypothesis $h\in\{0,1\}$, with distinct $p_0,p_1\in[0,1]$. Equivalently, the pair $(X,Y)$ is generated from a joint distribution $P_{XY}^h$ under which the marginals are uniform but have correlation $\rho_h=1-2p_h$ so that $X\oplus Y$ has i.i.d. Bernoulli$(p_h)$ entries. Alice (resp. Bob) sends a $k_A$-bit (resp. $k_B$-bit) message to a referee, who must determine $h$ with a guess $\widehat{H}$ (note that this is a random variable as it depends on the observations). Note that taking $k_B=n$ also includes the “one-way” communication model where Bob himself is the referee. This setting with uniform marginals correlated according to the hypothesis is also a common choice [30, 31, 40, 54] as it clearly highlights the distributed aspect of the problem: Alice and Bob themselves have no information about the hypothesis, but with communication, they are able to make a non-trivial decision.

This is an instance of the widely studied problem of distributed hypothesis testing in information theory, where the primary focus has been on characterizing the optimal trade-off between the error probability and the amount of communication (see the classical survey [26] for more background). The optimal encoding is often a typicality-based random construction [1 Han87, 52, 58] that has a prohibitively high space and memory requirement. We focus on the correlation testing setup as described above, and we consider a conceptually simple protocol where Alice and Bob both send binary linear sketches of their observations, i.e., Alice sends $AX$ using a rank-$k_A$ matrix $A$ and Bob sends $BY$ using a rank-$k_B$ matrix $B$. In addition to being easy to implement [3], they emerge as natural protocols to analyze in sequence, as described in § 1, linear-ear sketches are known to be optimal to reconstruct the modulo-2 sum [36], which is a sufficient statistic to test correlation of binary vectors. Moreover, for this correlation testing problem, they were shown to outperform typicality-based constructions for a subset of $p_0,p_1\le\frac{1}{2}$ [28, 29]. We show that when $p_0\ge\frac{1}{2}\ge p_1$ (or by symmetry $p_1\ge\frac{1}{2}\ge p_0$) truncation is the best linear sketch, that is, no linear sketch outperforms simply sending a prefix of the input. This is similar in spirit to the work of Amari [7] (see also [17]), who showed, by computing the Fisher information of $(f(X),g(Y))$, that truncation is asymptotically optimal among a class of “linear-threshold encodings” (which are different from the class of linear sketches that we consider) for estimating the correlation when $X,Y$ are nearly independent.

Our main result is stated formally below in Theorem 1. We show that among all possible choices of linear sketches of Alice and Bob (which could, in principle, be different), the optimal choice is for both to truncate the observation. Recall that “optimality” is in terms of Blackwell dominance (as described in § 2) which has the following implication here. In a hypothesis testing setup, there are two kinds of errors, type-I and type-II, with probabilities $e_h = P_{XY}^h\{\widehat{H} \ne h\}$ for $h = 0,1$ respectively. Every choice of encoder (mapping $X$ and $Y$ to messages) and decoder (mapping messages to a decision $\widehat{H}$) achieves a particular error probability pair $(e_0,e_1)$. Hence, if we show that $(X_{[k]},Y_{[k]})$ Blackwell-dominates $(AX,BY)$, then every $(e_0,e_1)$ that can be attained by the linear sketch $(AX,BY)$ using some decoder can also be attained by the truncated message $(X_{[k]},Y_{[k]})$. In particular, $(X_{[k]},Y_{[k]})$ can then do at least as well in both type-I and type-II error probability as any linear sketch.

This is exactly the statement of Conjecture 1 in [23], where it was proved for the special cases (1) $p_0+p_1=1$ and (2) $p_0=1/2$ or $p_1=1/2$. We prove Theorem 1 in two steps: we first show in Proposition 1 that both Alice and Bob using the same linear sketch is always better (for any $p_0,p_1$) than using different sketches. This is already known [23 Theorem 1], but we repeat the proof as it is short and illustrates the idea of constructing an explicit kernel to show Blackwell dominance. Then, we show that when the correlations under the hypotheses are of opposite signs, truncation is the best choice of this same linear sketch.

Proof. Let $Z := X \oplus Y$. We prove the statement by constructing a kernel to simulate $(AX,BY)$ from $A(X \oplus Y) = AZ =: U$ under hypothesis $h = 0,1$. Generate $W$ uniformly on $\mathbb{F}_2^n$, i.e. i.i.d. $\operatorname{Bernoulli}(1/2)^{\otimes n}$, independent of $Z$. Then $(AW \oplus U,BW)$ has the same distribution as $(AX,BY)$. We are done since the described kernel does not use the hypothesis $h$; we only generate a uniform vector $W$, independent of everything else. The other side holds similarly. $\square$

Note that Proposition 1 not only implies that the same linear sketch should be applied by both Alice and Bob, but also that the modulo-2 sum $AX \oplus AY$ of the sketches is sufficient for this problem, in lieu of the full pair $(AX,AY)$. This is perhaps unsurprising, as the sum $X \oplus Y$ is a sufficient statistic for the hypothesis test over $(X,Y)$. Thus, our original problem, namely identifying the best linear sketches $(AX,BY)$ for testing $X \oplus Y \sim\operatorname{Bernoulli}(p_0)^{\otimes n}$ versus $\operatorname{Bernoulli}(p_1)^{\otimes n}$, reduces to simply identifying the best linear sketch $AZ$ for testing $Z \sim\operatorname{Bernoulli}(p_0)^{\otimes n}$ versus $\operatorname{Bernoulli}(p_1)^{\otimes n}$.

We can assume w.l.o.g. that the rank-$k$ matrix $A$ is equal to $[I\mid\widetilde{A}]$ for some $k \times(n-k)$ matrix $\widetilde{A}$. Truncation is the best linear sketch if and only if $Z_{[k]} \succeq Z_{[k]} \oplus\widetilde{A}Z_{[k]^c}$ for all $\widetilde{A}$. We will instead show a stronger result in Proposition 2, namely that $Z_{[k]} \succeq Z_{[k]} \oplus V$ for any $V$ independent of $Z_{[k]}$ but with possibly different distributions $P_V^0$ and $P_V^1$ under the respective hypotheses, when $p_0,p_1$ are on opposite sides of $1/2$.

It is worth remarking that $V$ can carry useful information about the hypothesis, so it is not trivial that adding $V$ to $U$ should not help (and indeed, we will see in the proof that $U \succeq U \oplus V$ can fail when $p_0,p_1$ are on the same side of $1/2$). Theorem 1 clearly follows as an immediate corollary of Propositions 1 and 2. All that remains is to prove Proposition 2, which follows from two short lemmas. First, note that by Fact 1, Proposition 2 is equivalent to the claim that for all distributions $P_V^0,P_V^1$ over $\mathbb{F}_2^k$ and all $f$-divergences, we have $D_f(P_U^1 \mathbin\Vert P_U^0) \ge D_f(P_{U\oplus V}^1 \mathbin\Vert P_{U\oplus V}^0)$ if and only if $p_0,p_1$ are on opposite sides of $1/2$. We show in Lemma 1 that it is sufficient to check this inequality for $V$ that is deterministic under both hypotheses, and that it is sufficient to take one of these deterministic values to be $0$. We then construct an explicit transition kernel for a single bit in Lemma 2 that suffices when $V$ is deterministic, putting the two together to complete the proof of Proposition 2 below.

Proof. The assumption $U \succeq U \oplus V_v$ is equivalent to

for every $f$-divergence (i.e., for all convex $f$ with $f(1)=0$). Now for arbitrary $P_V^h$, $h=0,1$, let $V \sim P_V^h$ be independent of $U$, and let $D_f$ be any $f$-divergence. By the joint convexity of $D_f$, we have

with the equality obtained by applying the bijection $u \mapsto u \oplus v_0$ to both arguments, which does not change $D_f$. The term on the right-hand side of (3), by assumption, is at most $D_f(P_U^1 \mathbin\Vert P_U^0)$, and hence, applying Fact 1 again gives the desired conclusion. $\square$

Proof. We want to construct a transition kernel $K$ that maps $\operatorname{Bernoulli}(p_0)$ to itself, but $\operatorname{Bernoulli}(p_1)$ to $\operatorname{Bernoulli}(1-p_1)$ as in (1). Writing this in matrix notation, we want to find a stochastic matrix

with $a,b\in[0,1]$ so that

@page 8/21 starts_mid=1 ends_mid=1 Since both sides have rows summing to 1, it suffices to check equality for the first column, i.e.,

As $p_0 \ne p_1$, this has the unique solution $a = p_1(1-2p_0)/(p_1-p_0)$, $b = (1-p_0)(2p_1-1)/(p_1-p_0)$. It is easy to check that they both lie in $[0,1]$ if and only if $p_0,p_1$ are on opposite sides of $1/2$ (including $1/2$ itself), as claimed.

We now put these lemmas together to complete the proof of Proposition 2.

Proof of Proposition 2. If $p_0,p_1$ are strictly on the same side of $1/2$, then taking $V=V_v$ with $v=(1,0,\ldots,0)$, we have, by Lemma 2, that $U \succeq U\oplus V_v$ if and only if $p_0,p_1$ are on opposite sides of $1/2$.

As for sufficiency, suppose $p_0,p_1$ are on opposite sides of $1/2$. By Lemma 1, it is enough to show that $U \succeq U\oplus V_v$ for every deterministic $v\in\mathbb{F}_2^k$ (recall that $V_v$ is deterministically equal to $v$ under $h=1$ and equal to $0$ under $h=0$). As the coordinates of $U$ are independent, we can simulate each of them separately, as follows. For the coordinates at which $v$ has entry 0, there is nothing to do. For the coordinates at which $v$ has entry 1, use the kernel $K$ from Lemma 2, and we are done. Let $K_v$ denote this channel simulating $U\oplus V_v$ from $U$ for a deterministic $v$.

We now show how this also gives an explicit kernel from $U$ to $U\oplus V$ for arbitrary distributions $P_V^h$, $h=0,1$. Let $v_0$ and $v_1$ be two samples drawn from distributions $P_V^0$ and $P_V^1$ respectively, with any coupling between them. Pass $U$ through kernel $K_{v_0\oplus v_1}$, and add $v_0$ to the resulting vector. The resulting vector has distribution $P_{U\oplus v_h}^h$ under hypothesis $h$. Averaging this over all sampled $v_0\sim P_V^0$ and $v_1\sim P_V^1$ gives a vector with distribution $P_{U\oplus V}^h$ when the hypothesis is $h$, and we are done. For the special cases (1) $p_0+p_1=1$ and (2) $p_0=1/2$ or $p_1=1/2$ applied to $(U,V)=(Z_{[k]},\widetilde{A}Z_{[k]^c})$ for $Z\sim\operatorname{Bernoulli}(p_h)^{\otimes n}$, this recovers the kernels in [23] for some coupling of $v_0,v_1$ above.

We have thus shown that truncation is the best linear sketch for the distributed testing for correlations of opposite signs from i.i.d. samples. Importantly, we require the independence of $Z_I$ and $Z_{I^c}$ for $I=[k]$ under each hypothesis to use Proposition 2. In the next section, we consider a Boolean function evaluation problem, where we no longer have this independence. Nonetheless, we show that a certain “opposite monotonicity” assumption on the joint distribution of $Z_I$ and $Z_{I^c}$ suffices, generalizing Proposition 2.

Evaluating unate Boolean functions from sketches

Let $Z$ be uniform on $\mathbb{F}_2^n$ and suppose that we wish to evaluate $f(Z)$ without observing $Z$ directly. Instead, we are given a rank-$k$ linear sketch $AZ$. Previous work [21, 37, 62] has largely focused on characterizing the trade-off between the size of the sketch and the approximation error through assumptions on the Fourier structure of the target function $f$. Instead, we show that as long as $f$ satisfies a monotonicity property, namely that it is unate (as defined below), no rank-$k$ linear sketch performs better than truncation to some $k$ input coordinates (which, naturally, depends on $f$).

This can be viewed as a binary hypothesis testing problem, with the two hypotheses corresponding to $f(Z)=0$ and $f(Z)=1$. The conditional distributions of $Z$ under these two hypotheses have different supports (as $f(z)$ is necessarily exactly one of the values 0 and 1 for all $z$), and hence, we can achieve zero error with access to $Z$ (this is a rewording of the trivial observation that we can exactly evaluate $f(Z)$ if we know $Z$). However, the conditional distributions of an observation $S$ based on $Z$, such as a linear sketch $AZ$, induced by the two hypotheses may not have disjoint supports, making the problem non-trivial.

For an observation $S$ obtained from $Z$, let

denote the minimum probability of error in evaluating $f(Z)$ from $S$. The result below shows that among all possible linear sketches $S$ of $Z$, truncation minimizes this error probability. Further, truncation is also optimal for any decision problem in which the unknown quantity is $f(Z)$ and must be estimated from a linear sketch of $Z$.

To prove the theorem, we use the following generalization of the truncation result from the previous section. Note that conditioning on the function value destroys the independence of coordinates, which was necessary for Proposition 2. Instead, Proposition 3 only requires the joint distributions (conditioned on the function value) to satisfy a certain coordinate-wise monotonicity property, which, as we shall see, follows from the unateness of $f$.

Proof. By Fact 1, it suffices to compare the $E_\gamma$-divergences for every $\gamma\ge0$, i.e., we want to show that $E_\gamma(P^1_U \mathbin\Vert P^0_U) \ge E_\gamma(P^1_{U\oplus V} \mathbin\Vert P^0_{U\oplus V})$. Let $U_{-\ell} \in\mathbb{F}_2^{k-1}$ denote the vector $U$ with its $\ell$-th coordinate removed (and similarly $V_{-\ell}$ is $V$ without $V_\ell$). We first show that for any arbitrary function $W_\ell$ taking values in some alphabet $W$ of the remaining coordinates $(U_{-\ell},V_{-\ell})$, replacing $U_\ell$ with $U_\ell\oplus V_\ell$ cannot increase the desired $E_\gamma$-divergence. That is, we show that

where $W_\ell$ is any function of $(U_{-\ell},V_{-\ell})$. We apply (5) successively by taking $W_1=U_{-1}$, $W_k=U_{-k}\oplus V_{-k}$, and at step $\ell=2,\ldots,k-1$,

It is easy to check that with this choice of $W_\ell$, the right-hand side at each step is the left-hand side at the next step, starting from $U$ on the left at $\ell=1$ and ending with $U \oplus V$ on the right at $\ell=k$. It therefore remains to prove (5) for arbitrary choices of $W_\ell$.

To see this, fix $w \in\mathcal{W}$ and define $a_{ij}$ for $i,j=0,1$ as

By the (coordinate-wise opposite) monotonicity assumption, we have that $a_{1j} \ge a_{0j}$ for both $j=0,1$, as marginalizing over $(U_{-\ell},V_{-\ell})$ that have $W_\ell=w$ preserves monotonicity.

Now we evaluate the left-hand side of (5) in terms of $a_{ij}$'s. To obtain the joint distribution of $(U_\ell,W_\ell)$, we have to marginalize $a_{ij}$ over $V_\ell=0,1$ in each term, and hence the contribution of the $W_\ell=w$ term to the left-hand side is

Similarly, for the right-hand side, we require the joint distribution of $(U_\ell\oplus V_\ell,W_\ell)$, for which we marginalize over $(U_\ell,V_\ell)$ with the same value of $U_\ell\oplus V_\ell$, i.e., $U_\ell=V_\ell$ in one term and $U_\ell\ne V_\ell$ in the other. Hence, the contribution of the $W_\ell=w$ term to the right-hand side is

Thus, we are done if we can show that the expression in (6) is at least that in (7). But this follows from the convexity of the map $z \mapsto[z]_{+}$: set $x=a_{00}+a_{01}$ and $y=a_{10}+a_{11}$. If $x=y$ there is nothing to do (as monotonicity forces $a_{00}=a_{10}$ and $a_{01}=a_{11}$). If $x \ne y$ then set $\lambda=(a_{10}-a_{00})/(y-x)$. Note that by the monotonicity assumption, $\lambda\in[0,1]$. The left-hand side (6) is then $[x]_{+}+[y]_{+}$, while the right-hand side (7) is

which is upper bounded by $[x]_{+}+[y]_{+}$ by the convexity of $z \mapsto[z]_{+}$ applied to each term. As this holds for every $w$, we have proved (5), and this completes the proof. $\square$

Proposition 3 also immediately recovers Theorem 1. Indeed, writing $A=[I\mid\widetilde{A}]$ w.l.o.g. (as the correlation testing problem is symmetric in input coordinates), we can take $U=Z_{[k]}$ and $V=\widetilde{A}Z_{I^{c}}$ in Proposition 3. It is immediately clear that when the Bernoulli biases are on opposite sides of $1/2$, the required monotonicity assumption holds: $U$ and $V$ are independent under both hypotheses, so the joint probability being increasing/decreasing in $Z_i$ depends on the bias being greater/smaller than $1/2$ respectively. We thus have $U=Z_{[k]} \succeq U\oplus V=AZ$ as a direct consequence.

Proof of Theorem 2. Assume that $f$ is not constant, as the constant case is trivial. For any matrix $A$ with information set $I$ of size $k$, take $U=Z_I$ and $V=\widetilde{A}Z_{I^c}$ with $\widetilde{A}=A_I^{-1}A_{I^c}$. It suffices to check that the joint distributions $P_{UV}^{h}$ of $(U,V)$ conditioned on $f(Z)=h$ for $h=0,1$ respectively satisfy the required coordinate-wise monotonicity properties. Then, as $Z$ is uniform on $\mathbb{F}_2^n$, we have the joint distributions

where $f(u,w)$ denotes the evaluation of $f$ at $z$ with $z_I=u$ and $z_{I^c}=w$. Note that we can write the above cardinality for $h=0,1$ respectively as $\sum_{w\in\mathbb{F}_2^{n-k}:\widetilde{A}w=v}(1-f(u,w))$ and $\sum_{w\in\mathbb{F}_2^{n-k}:\widetilde{A}w=v}f(u,w)$. Hence, for each coordinate of $u$, $P_{UV}^{1}$ inherits the direction of monotonicity of $f$, while $P_{UV}^{0}$ has the opposite direction (such a direction for each coordinate exists as $f$ is unate). To deal with this, let $d \in\mathbb{F}_2^k$ be such that $u \mapsto f(u \oplus d,w)$ is coordinate-wise non-decreasing for every $w$, and let $\widetilde{U}=U\oplus d$. Then, $P_{\widetilde{U}\oplus V}^{h}$ for $h=0,1$ exactly satisfy the monotonicity assumption of Proposition 3 and hence, $\widetilde{U}\succeq\widetilde{U}\oplus V$. Since $\widetilde{U}=U\oplus d$ is an invertible transformation of $U$ and $\widetilde{U}\oplus V=U\oplus V\oplus d$ is an invertible transformation of $U\oplus V$, we also have $U\succeq U\oplus V$, i.e., $Z_I\succeq AZ$, completing the proof.

Thus, we have shown that to evaluate unate functions from binary linear sketches, the best such sketch is simple truncation. It is easy to see that this no longer holds if $f$ is not unate: consider the simple example $f(z_1,z_2)=z_1\oplus z_2$. Then the binary linear sketch obtained using $A=[1\ \ 1]$ exactly recovers $f(z)$ for all $z$, while truncation to either $z_1$ or $z_2$ cannot do better than an error probability of $1/2$ for inputs uniform on $\mathbb{F}_2^2$.

Suboptimality of linear sketches for connectivity testing

We now use Theorem 2 to give a simple example where linear sketches can be shown to be significantly worse than arbitrary functions, by using truncation as an easy intermediary. Linear sketches are commonly used in distributed settings, and one such problem is that of testing graph connectivity [5, 61]. We consider a one-way communication version of the problem: Alice and Bob observe graphs $G$ and $H$ respectively on the same vertex set, and are unaware of each other’s graphs (otherwise the problem is trivial). Alice sends a message as a function of $G$ to Bob, who wants to decide whether $G\cup H$ is connected. Sun and Woodruff [56] showed that randomized one-way protocols for this problem require $\Omega(n\log n)$ bits to have error probability (over the randomness of the protocol) at most some small constant, say $1/10$, for every pair $(G,H)$ (and this lower bound can be achieved by considering a deterministic protocol, namely sending a spanning forest of $G$ [33]).

In our example, we consider a (partial) distributional version where $G$ is a uniformly random subgraph of a specific complete bipartite graph (as described below), and we want the error probability (over the randomness of $G$) to be at most $1/10$ for every $H$. We show that truncation (and hence all binary linear sketches) still requires $\Theta(n\log n)$ bits, while we can construct a simple nonlinear message that does so with $O(\log n)$ bits.

More precisely, we consider a specific bipartite vertex set with $v$ left vertices and $2^v$ right vertices, giving a total of $n=v+2^v$ vertices and $m=v2^v$ possible edges. Alice’s graph $G$ has each of the $m$ edges present independently with probability $1/2$. Bob’s graph $H$ can be any fixed graph on the same vertex set.¹ We represent $G$ using its edge-indicator vector $Z\in\mathbb{F}_2^m$, with $Z_i=1$ if the $i$-th edge is present. A binary linear sketch that is a $k$-bit message is then $AZ$ for some rank-$k$ matrix $A$. Given a message $S$ and a decoder $g$ that maps $(S,H)$ to 1 for “connected” and 0 otherwise, define the error probability

(ii) On the other hand, if $\phi(Z)=AZ$ is a $k$-bit linear sketch of $Z$, then to have $\widetilde{e}_H(AZ,g)\le1/10$ for every $H$, it is necessary that $k\ge m/2=\Omega(n\log n)$.

Proof. Upper bound in (i). We provide the claimed deterministic protocol here and relegate its analysis to Appendix § 9.§ 1. If there are at most three isolated right vertices and all remaining (right and left) vertices form one connected component, then Alice sends the labels of the isolated right vertices. Otherwise, Alice declares failure using a special message. Upon receiving a non-failure message from Alice, Bob immediately knows the component partition of $G$ (he knows the locations of the isolated vertices and that the remaining are connected), and is thus able to determine whether $G\cup H$ is connected or not. In Appendix § 9.§ 1, we show that the probability of Alice sending a failure message is at most $1/10$ for sufficiently large $v$.

Lower bound in (ii). It is enough to show the lower bound for a specific $H$; we take the empty graph $H=\varnothing$. Thus, Bob wants to evaluate $f(Z)=1\{G\text{ is connected}\}$. Since $f$ is monotone and hence unate, Theorem 2 says that truncation to an information set $I$ of $A$ performs at least as well as $AZ$. Thus, for every decoder $g$, we have

where $\widetilde{e}_{\varnothing}(AZ,g)$ is the error probability of using decoder $g$ with the linear sketch to test if $G$ is connected (as defined in (8)), while $e_f(AZ)$ is the minimum error probability over all decoders to test if $G$ is connected (as defined in (4)). Hence, it suffices to obtain a lower bound to the error probability of truncation. To do so, let $p=\Pr\{G\text{ is connected}\}=\mathbb{E}[f(Z)]$, and let the random variable $Q=\mathbb{E}[f(Z)\mid Z_I]$. Note that the smallest possible error probability conditioned on $Z_I$ is $\min\{Q,1-Q\}$, and hence, $e_f(Z_I)=\mathbb{E}[\min\{Q,1-Q\}]$. Simply lower bounding $\min\{a,b\}$ for $0\le a,b\le1$ by $ab$, we have

The right-hand side, with some rearrangement and using the fact that $\mathbb{E}[Q]=\mathbb{E}[f(Z)]=\mathbb{E}[f(Z)^2]$ as $f(z)\in\{0,1\}$, can be written as $\operatorname{Var}(f(Z))-\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$. Hence, to complete the proof, it suffices to show that the variance of $f(Z)$ that is explained by $Z_I$, namely $\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$, cannot be too close to $\operatorname{Var}(f(Z))$. The desired bound is given by Lemma 3, which is a specialized version of [24 Theorem 1.1]. We give a self-contained proof for Lemma 3 in Appendix § 9.§ 2.

Note that $\operatorname{Var}(f(Z))=\mathbb{E}[f(Z)]-\mathbb{E}[f(Z)]^2=p-p^2$. Thus, using Lemma 3, we have that for $|I|=k$,

We show in Appendix § 9.§ 3 that $p=\Pr\{G\text{ is connected}\}$ goes to $1/e$ as $v\to\infty$, and hence, for sufficiently large $v$, we have $p(1-p)>1/5$ as $1/e(1-1/e)>0.23>1/5$, so $k\ge m/2$ is necessary for the lower bound to be smaller than $1/10$. □

Thus, we have an example where the limitations of linear sketches can be easily established by deferring to the proxy of truncation: arbitrary nonlinear functions can achieve a small constant error using only $O(\log n)$ bits of communication, but truncation (and consequently, by Theorem 2, all linear sketches) requires $\Theta(n\log n)$ bits, where $n$ is the number of vertices of the graph.

Acknowledgements

A.G. would like to thank Amit Rajaraman for a careful reading of the introduction and for providing feedback that improved clarity and organization.

AI methodology

Coming from an information theory background and being unfamiliar with the broad theoretical computer science literature, the authors used AI tools (OpenAI’s GPT-6.1 “Sol”) to help with identifying and making sense of related work, particularly for the presentation in the introduction. These tools were also used to identify the applications to graph connectivity testing and evaluation of Boolean functions (which were selected from a long list of suggestions and details worked out by the authors). All theoretical results are due to the authors directly, as is all of the writing. GPT-6.1 was also used to identify typos and grammatical errors, which were subsequently corrected by the authors.

References

Appendix: Technical proofs for graph connectivity analysis

Here we provide details of technical intermediate results that were skipped in the main body of the paper to allow for a coherent presentation of the most relevant ideas.

Analysis of nonlinear protocol for graph connectivity

We complete the proof of Theorem 3 by showing that the nonlinear protocol described achieves an error probability at most $1/10$ for sufficiently large $v$, using $3v+3=O(\log n)$ bits. The proposed deterministic protocol is as follows: If there are at most three isolated right vertices and all remaining (right and left) vertices form one connected component, then Alice sends a leading $0$, followed by two bits to specify the number of isolated right vertices (which is one of $0,1,2,3$), and then the labels of the isolated right vertices (this requires $v$ bits each; she sends at most three). Otherwise, Alice declares failure by simply sending a single bit $1$. Upon receiving a non-failure message (i.e., not the single bit $1$) from Alice, Bob immediately knows the component partition of $G$ (he knows the locations of the isolated vertices and that the remaining are connected), and is thus able to correctly determine whether $G\cup H$ is connected or not. Bob can declare arbitrarily upon receiving a failure message from Alice.

Thus, it is enough to bound the probability that Alice declares failure and show that it is at most $1/10$ for sufficiently large $v$. As the $v$ edges from a given right vertex are chosen uniformly randomly, the probability that a right vertex is isolated is $1/2^v$, independently of the other right vertices. Hence, the probability that any fixed four right vertices are all isolated is $1/2^{4v}$. Taking a union bound over all choices of four right vertices, we have

which goes to $1/24$ as $v$ goes to infinity.

Next, we consider the probability that the remaining vertices do not form a single connected component. Fix two distinct left vertices. Each right vertex is connected to both these left vertices with probability $1/4$, hence the probability that this pair of left vertices has no common neighbour is $(3/4)^{2^v}$. Taking a union bound over all pairs of left vertices, we have that

which also goes to zero as $v$ gets large. If all pairs of left vertices have a common neighbour, then all left and non-isolated right vertices belong to the same connected component. Hence, the probability that Alice declares failure is at most the sum of the above, which goes to $1/24$ and is thus smaller than $1/10$ for sufficiently large $v$. □

Proof of variance reduction lemma

We restate Lemma 3 then provide a self-contained proof.

Proof. We use techniques from Fourier analysis, see [48, 37] for a more detailed exposition. For a subset $J \subseteq[m]$, define the character $\chi_J(z) = \prod_{\ell\in J}(-1)^{z_\ell}$. Characters form an orthonormal basis for the set of functions from $\mathbb{F}_2^m$ to $\mathbb{R}$, in particular, $\mathbb{E}[\chi_J(Z)\chi_K(Z)] = \mathbf{1}\{J=K\}$ for $J,K \subseteq[m]$. The Fourier expansion of $f$ is

where $\widehat{f}(J)$ are the Fourier coefficients of $f$, which are real-valued. Observe that $\mathbb{E}[\chi_J(Z)\mid Z_I]$ for $I\subseteq[m]$ is equal to $\chi_J(Z)$ if $J\subseteq I$ and $0$ otherwise, as the unconditioned uniform bit is averaged over. Hence, by linearity of expectation, we have

the only change from above being the restriction to $J\subseteq I$ (in particular, if $I=[m]$, we have $\mathbb{E}[f(Z)\mid Z]=f(Z)$ and if $I=\varnothing$ is the empty set, we have $\mathbb{E}[f(Z)]=\widehat{f}(\varnothing)$). We now compute the variance of the conditional expectation $\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$, i.e.,

thanks to the orthonormality of $\chi_J$ (with $\varnothing$ excluded as $\chi_{\varnothing}=1$ and has zero variance). In particular, taking $I=[m]$ gives $\operatorname{Var}(f(Z))=\sum_{J\ne\varnothing}\widehat{f}(J)^2$.

We now compare the two variances, for which it will be useful to define, for edge $\ell\in[m]$, the quantity $a_\ell=\sum_{J\ni\ell}\widehat{f}(J)^2/|J|$. First note that the sum of all $a_\ell$’s is $\operatorname{Var}(f(Z))$, as

Since the edges of a complete bipartite graph are symmetric, $a_\ell=\operatorname{Var}(f(Z))/m$ for each $\ell$. On the other hand, the variance of the conditional expectation is, by (10),

Observe that the term being summed on the right-most expression in (12), for each $\ell\in I$, is at most $a_\ell$, and hence, $\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$ is at most $\sum_{\ell\in I}a_\ell=|I|/m\operatorname{Var}(f(Z))$. This completes the proof.

The above definition of $a_\ell$ can be motivated as follows. For a nonempty set $J\subseteq[m]$, “split” its weight $\widehat{f}(J)^2$ equally among the $|J|$ edges in $J$. For edge $\ell\in[m]$, $a_\ell$ is the total weight assigned to edge $\ell$ from all sets $J$ by such a splitting. Summing $a_\ell$ over all edges $\ell\in[m]$ yields the full variance $\operatorname{Var}(f(Z))$, hence $a_\ell$ can be considered the contribution of edge $\ell$ to the total variance of $f$. However, for a given $I$, the variance of the conditional expectation $\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$ includes contributions from edges $\ell\in I$ that are not $a_\ell$ (which includes shares of weights from all sets containing $\ell$), but rather, only the shares of weights from sets containing $\ell$ that are also themselves contained in $I$. Thus, summing $a_\ell$ over all edges $\ell\in I$ gives an upper bound to $\operatorname{Var}(\mathbb{E}[f(Z)\mid Z_I])$.

Probability of random subgraph connectivity

As stated in the proof of Theorem 3, we show that the graph $G$ (a uniformly random subgraph of the complete bipartite graph with $v$ left vertices and $2^v$ right vertices) is connected with probability approaching $1/e$ as $v \to\infty$.

We showed in Appendix § 9.§ 1 that the probability that all left and non-isolated right vertices do NOT all belong to the same connected component is at most $\binom{2^v}{2}(3/4)^{2^v}$, which goes to zero as $v \to\infty$ (see (9)). Hence, in the limit as $v \to\infty$, the probability that $G$ is connected is simply the probability that $G$ has no isolated right vertices. Each of the $2^v$ right vertices is isolated with probability $1/2^v$ (independently), as each of its $v$ edges is picked with probability $1/2$. Hence, the probability that $G$ has no isolated right vertices is $(1-1/2^v)^{2^v}$, which has limit $1/e$ as $v \to\infty$, and we are done.

Appendix: Notation summary

For completeness, here is notation that we use throughout the paper. We write $[n]=\{1,\ldots,n\}$ and $[t]_+=\max\{t,0\}$. $\mathbb{F}_2$ denotes the field given by the set $\{0,1\}$ with addition $\oplus$ and multiplication modulo 2. Uppercase italicized letters play multiple roles: $S,U,V,W,X,Y,Z$ refer to random variables; $A,B$ refer to matrices; $G,H$ refer to graphs; $I,J,K$ denote coordinate index sets (which are subsets of $[n]$ or $[m]$); $K$ refers to a transition kernel, represented by a stochastic matrix (non-negative entries with rows summing to one). Given a vector $x \in\mathbb{F}_2^n$, a matrix $A \in\mathbb{F}_2^{k \times n}$ and subset $I \subseteq[n]$, $x_I$ denotes the subvector indexed by $I$ and $A_I$ denotes the submatrix formed by the columns indexed by $I$. $I^c$ denotes the complement of set $I$, which in our case is always $[n]\setminus I$. The boldface letter $\mathbf{I}$ denotes the identity matrix (which is always $k \times k$ here), while $\mathbf{1}$ denotes the indicator function that evaluates to 0 or 1 accordingly as its argument is false or true.

$P,Q$ refer to probability distributions with subscripts possibly used to clarify the random variable when important (e.g., $P_X$ is the probability distribution of random variable $X$) and superscripts possibly denoting a hypothesis $h=0,1$. Calligraphic letters (e.g. $\mathcal{W},\mathcal{Z}$) denote the alphabet that a random variable (e.g. $W,Z$) takes values in (with the exception of $\mathcal{R}_{k,n}$ in § 1.3). Blackwell dominance is represented using $\succeq$. We use $\epsilon$ to denote various notions of error, while $e$ denotes the standard mathematical constant. We write $D_f(\cdot\mathbin{\|}\cdot)$ and $E_\gamma(\cdot\mathbin{\|}\cdot)$ to denote the $f$- and $E_\gamma$-divergences between two distributions. We use $\Pr\{\cdot\}$ to denote the probability of an event and $\mathbb{E}$ and $\operatorname{Var}$ to denote the expectation and variance, all computed over the joint distribution of all random variables involved. We use $\operatorname{Bernoulli}(p)$ to refer to the Bernoulli distribution with bias $p$: $Z$ distributed as $\operatorname{Bernoulli}(p)$ (abbreviated as $Z \sim\operatorname{Bernoulli}(p)$) takes value 1 with probability $p$ and 0 otherwise. The product distribution is denoted as $\operatorname{Bernoulli}(p)^{\otimes n}$: $Z \sim\operatorname{Bernoulli}(p)^{\otimes n}$ means that $Z=(Z_1,\ldots,Z_n)$ with each $Z_i$ independently and identically distributed (i.i.d.) as $\operatorname{Bernoulli}(p)$.