On the suboptimality of linear codes for binary distributed hypothesis testing

Adway Girish; Emre Telatar; Robinson D. H. Cung

REVIEW 3 major objections 4 minor 1 cited by

Linear codes are strictly suboptimal for a family of binary distributed hypothesis tests, where the best linear scheme is simple truncation.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 10:17 UTC pith:PHTVP635

load-bearing objection A clean, genuinely new result on linear codes for binary DHT, with a fixable gap in the analytic suboptimality proof — worth reviewing. the 3 major comments →

arxiv 2601.10526 v2 pith:PHTVP635 submitted 2026-01-15 cs.IT math.ITmath.STstat.TH

On the suboptimality of linear codes for binary distributed hypothesis testing

Adway Girish , Robinson D. H. Cung , Emre Telatar This is my paper

classification cs.IT math.ITmath.STstat.TH MSC 94A1594A24

keywords distributed hypothesis testinglinear codestruncationStein exponentBlackwell orderrandom codingDSBSopposite correlations

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a two-agent binary hypothesis test in which each agent compresses its n binary observations with a linear code and sends the result to a central decision maker. Its main result is that when the two hypotheses give correlations of opposite sign, or when one hypothesis is independence, the best possible linear code is trivial truncation: keeping the first k bits of each sequence dominates any pair of linear codes whose ranks are at most k. The paper then shows that even this best linear scheme is strictly suboptimal: a classical random-quantization coding scheme achieves a strictly larger Stein exponent at rates close to 1, so no linear code can be asymptotically optimal in that regime. This matters because earlier work had made linear codes look like the natural practical choice for binary distributed hypothesis testing; the paper identifies precisely when that intuition fails.

Core claim

The central claim is Theorem 2: for testing DSBS(p) against DSBS(1/2), DSBS(1/2) against DSBS(p), or DSBS(p) against DSBS(1-p), the statistic formed by the first k positions of each sequence, (X^k, Y^k), dominates, in the Blackwell order, any pair of linearly compressed messages (GX^n, HY^n) whose ranks are at most k. In words, truncation is the best linear code in these three cases. The proof constructs, for any full-rank generator matrix, a random channel that exactly simulates the compressed messages from the truncated observations under both hypotheses. The paper also proves that the two agents never need different linear codes: G(X^n xor Y^n) dominates (GX^n, HY^n), so the decision can

What carries the argument

The central mechanism is the Blackwell order on statistics together with a channel-simulation construction. To show one statistic dominates another, the paper builds a fixed conditional distribution that maps the dominating statistic to the dominated one simultaneously under both hypotheses, which proves the decision region of the former contains that of the latter. For Theorem 2, the needed simulation adds independent noise to the truncated mod-2 sum to reproduce the discarded coordinates. The asymptotic suboptimality argument uses the classical random-coding (random-binning) exponent for distributed hypothesis testing, in which each agent passes its observation through a binary symmetric c

Load-bearing premise

The load-bearing premise is that the optimal projection in the random-coding exponent calculation is the three-stage binary-symmetric-channel Markov chain X-U-V-Y with transitions BSC(alpha), BSC(alpha * alpha * p), BSC(alpha); the paper asserts this rather than derives it, and the derivative comparison near rate 1 is printed with the wrong limit (alpha -> 1/2, where the rate is 0, instead of alpha -> 0, where the rate is 1).

What would settle it

For testing DSBS(p) against DSBS(1/2) with small p and rate R = 1 - epsilon, solve the I-projection minimization numerically without assuming the asserted Markov-chain ansatz, and compare the resulting exponent to the truncation line (1 - epsilon) * d2(p || 1/2); if the optimized exponent fails to exceed the line for some p and epsilon, the claimed strict suboptimality of linear codes collapses.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

For testing DSBS(p) against DSBS(1/2), or the reverse, every linear scheme of rate R has type-II error exponent at most R * d2(p || 1/2), since truncation is the best linear code.
A classical random-quantization scheme beats that exponent at rates close to 1, so in that regime no linear code achieves the best Stein exponent.
The same conclusion holds, numerically, for testing DSBS(p) against DSBS(1-p) at sufficiently high rates.
Agents never lose optimality by using the same linear code and letting the decision maker work only with G(X^n xor Y^n), simplifying code design and the decision rule.
If Conjecture 1 is correct, the optimality of truncation, and therefore the suboptimality of all linear codes, extends to every pair of hypotheses with correlations of opposite signs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Because the two proved cases of Theorem 2 use different simulation constructions (for the convolution parameter 1/2 and for 1), a proof of Conjecture 1 will likely need a unified channel that interpolates between them; finding such a channel is the natural next objective.
The random-coding exponent curve is non-concave, so the improved exponent E_com obtained by concatenating an optimal random code with truncation is a general device: any distributed test whose exponent curve is non-concave can likely be improved this way.
For practical code design, the message is that short-blocklength linear encoders are unlikely to approach the fundamental exponent for tests involving opposite-sign correlations or independence; non-linear quantization or hashing deserves attention there.
The suboptimality appears only at high rates: the truncation line equals the random-coding exponent at rate 1 and the gap opens just below 1, so linear codes may still be near-optimal when communication is scarce.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

A clean, genuinely new result on linear codes for binary DHT, with a fixable gap in the analytic suboptimality proof — worth reviewing.

read the letter

The thing to know: this paper proves that for binary distributed hypothesis testing, using the same linear code at both agents is never worse, and that plain truncation is the best linear code for three specific correlation regimes—testing for independence, testing against independence, and equal-magnitude opposite signs. That truncation-optimality result is new; Haim and Kochman only handled positive correlations. The additional claim that linear codes are strictly suboptimal against classical random quantization for testing against independence is also new, but the submitted proof has a gap.

What I liked: Theorem 1 is a clean Blackwell-order argument, and I checked the channel constructions—they work. Theorem 2's proofs are genuinely clever, especially the even/odd row-weight split for the p1=1-p0 case. The authors are also honest: Conjecture 1 is clearly labeled as a conjecture, and the Section 5 numerical feasibility check is presented as numerical evidence, not proof. No fitted parameters, no circular reasoning.

The soft spot is Section 4. To show random coding beats truncation near rate 1, the paper needs E'_Han(1)=0. The displayed limit is wrong as written: it sends α→1/2, which corresponds to rate 0, not rate 1. With α→1/2 the ratio actually tends to (1−2p)^2, not 0. The correct endpoint is α→0, where the denominator h2'(α) blows up and the ratio does tend to 0. So the claim is likely true, but the proof as written is incomplete. Also, the identification of the optimal I-projection as the X–U–V–Y chain is asserted rather than derived; it is standard, but it deserves a derivation or a precise citation. The stress-test note's secondary point about the Markov relation is not load-bearing. For the equal-and-opposite case, the random-code comparison is numerical; that is fine as support, but the text should not imply it is analytic.

Bottom line: this is a subfield paper, not a general-audience one, but for people working on distributed hypothesis testing it is a solid step and the Blackwell-order framework will be reusable. Send it to a serious referee. I would want the derivative gap closed before publication, but the core results and most of the proofs deserve referee time.

Referee Report

3 major / 4 minor

Summary. The paper studies a binary distributed hypothesis testing problem in which two agents observe n i.i.d. pairs from DSBS(p_i) and communicate compressed versions of their observations to a central decision maker. The authors focus on linear compression schemes and analyze them through the Blackwell order of experiments. Theorem 1 shows that for any linear maps G,H, the statistic G(X^n⊕Y^n) is Blackwell-superior to the pair (GX^n,HY^n), so using the same linear code at both agents is at least as good as using different codes. Theorem 2 identifies three hypothesis families—DSBS(p) vs DSBS(1/2), DSBS(1/2) vs DSBS(p), and DSBS(p) vs DSBS(1−p)—for which simple truncation is the best linear code of a given rank. The paper then compares the truncation Stein exponent with Han's random-coding exponent. For testing against independence it claims an analytic proof that Han's scheme with symmetric BSC test channels strictly beats truncation at high rates; for the opposite-sign equal-magnitude case the same conclusion is supported by numerical experiments. A conjecture on general opposite-sign correlations is supported by small-case linear feasibility checks.

Significance. If the results hold, the paper makes a crisp and useful contribution: it identifies a natural, computationally attractive class of codes (linear codes) that is strictly suboptimal for a basic distributed hypothesis testing problem, in contrast to the earlier positive results for same-sign correlations. The Blackwell-order framework and the reduction to modulo-2 sums are elegant and likely to be reused. The proof of Theorems 1 and 2 is transparent, and the numerical feasibility study for Conjecture 1 is honest and reproducible. The main caveats are concentrated in Section 4, where the analytic proof of strict suboptimality has a fixable but real gap and the displayed exponent formula is internally inconsistent as stated. With those points corrected, the paper would be a worthwhile addition to the distributed hypothesis testing literature.

major comments (3)

[Section 4, derivative calculation] The proof of E'_Han(1)=0 evaluates lim_{α→1/2} of the derivative ratio [d/dα(1−h2(α∗α∗p))]/[d/dα(1−h2(α))]. But R=1−h2(α) tends to 0 as α→1/2, not to 1; the derivative at R=1 requires the limit α→0. The displayed calculation therefore does not establish the claimed behavior near rate 1, and the subsequent conclusion that the Han exponent lies above the truncation line at rates just below 1 is not justified as written. The correct endpoint is α→0, where the ratio indeed tends to 0 because h2'(α)→∞ while the numerator remains finite; please correct the proof and the displayed limit.
[Section 4, Eq. (2) and following paragraph] The definition of E_Han in Eq. (2) states that π must have the same UX, UY, and UV marginals as P^0, but the immediately following paragraph says that π* has the same UX, UV, and VY marginals and uses this to identify the Markov chain X−U−V−Y and to conclude E_Han=I(U;V). These are different constraint sets. The Markov-chain identification and the formula E_Han=I(U;V) are natural for the latter set (UX, UV, VY), not for the former set written in Eq. (2). Since the analytic comparison with truncation relies entirely on this formula, Eq. (2) must be corrected to the intended constraint set and the I-projection step should be stated explicitly.
[Abstract and Introduction, item 3] The Introduction and abstract claim that for both 'opposite signs of the same magnitude' and 'for/against independence', classical typicality-based quantization achieves a better Stein exponent than truncation, and hence any linear code is strictly suboptimal. The body provides an analytic derivation only for testing against independence (p1=1/2). For the opposite-sign equal-magnitude case the comparison is supported only by the numerical example in Fig. 3 and by the assertion that the plots are qualitatively identical for other parameters. No theorem is stated or proved for that case. Please either provide a proof or explicitly qualify the claim as numerical evidence, and adjust the abstract and Introduction accordingly.

minor comments (4)

[Section 3, proof of Theorem 2, case p1=1−p0] The line 'let U=Z^{k_e}⊕iZ^{k_e}' appears to contain a typo: it should be U=Z^{k_e}⊕i·1^{k_e} to match X^{k_e}⊕Y^{k_e}. With the printed formula, the constructed V does not have the claimed distribution.
[Section 4, Markov relations] The displayed relation U−◦−(X,Y)−◦−V is not implied by the factorization π*=P^1 f1(u,x)f2(v,y)f3(u,v); the relevant structure is the chain X−U−V−Y. Please remove or correct the displayed Markov relation.
[Figure 3] Please state explicitly whether the curve labeled E_Han for the symmetric BSC case is the analytic formula 1−h2(α∗α∗p) or a numerical solution of (2). The text seems to use both, which is confusing.
[Abstract] The abstract says Theorem 2 covers 'testing opposite signs of the same magnitude of correlation'; this is correct for the case p1=1−p0, but the general opposite-sign statement is only a conjecture. Please make this distinction explicit.

Circularity Check

0 steps flagged

No circularity found; derivations are self-contained, with a non-circular analytic gap at the Section 4 endpoint.

full rationale

The derivation chain is self-contained. Theorem 1 and Theorem 2 rest on explicit Blackwell-order channel constructions (Fact 1), and no fitted parameter is renamed as a prediction. In Section 4, E_Han(R) is computed for an explicit test-channel choice P_{U|X}=P_{V|Y}=BSC(α); the expression E_Han=I(U;V)=1−h2(α*α*p) at R=I(U;X)=1−h2(α) follows from the standard I-projection structure cited to Csiszár–Shields [CS04] and from the induced marginals, not from the target conclusion. The paper explicitly notes the BSC choice is 'not known to be the optimal choice of test channel', and the suboptimality claim only requires achievability, so no optimality input is smuggled in. The numerical feasibility checks in Section 5 support Conjecture 1 and are not used to prove Theorem 2. No load-bearing self-citations appear. The analytic suboptimality proof has a non-circular gap: the displayed limit for E'_Han(1) is taken as α→1/2 (rate 0) instead of α→0 (rate 1), so the endpoint derivative is not established as written; this is a correctness issue, not a reduction of the result to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No free parameters fitted to data. The central proofs use the standard Blackwell-order characterization and Han's random-coding exponent. The numerical experiments in §5 are supporting evidence for a conjecture, not part of the load-bearing proof.

axioms (4)

standard math Fact 1 (Blackwell order): U ⪰_B V iff there exists a channel P_{V|U} with P^i_V = P_{V|U} P^i_U for i=0,1.
Used throughout Section 3 to prove dominance by channel construction; cited to Blackwell [Bla51] and [PW25].
domain assumption Han's Stein exponent formula (2): E_Han = min_π D(π||P1_UXYV) over π with the same UX, UY, UV marginals as P0.
Adopted from [Han87]/[HA98]; not re-derived. Load-bearing for the random-coding comparison.
domain assumption The optimal I-projection π* has product structure f1(u,x) f2(v,y) f3(u,v), and for testing against independence simplifies to Markov chain X−U−V−Y with BSC transitions.
Section 4 paragraph after (2); this is asserted, not proved in the paper, and enables E_Han = I(U;V).
standard math For DSBS(p), X^n⊕Y^n is a sufficient statistic for (X^n,Y^n), and the co-located Stein exponent is d2(p0||p1).
Used in Section 2.2 and in the truncation exponent calculation.

pith-pipeline@v1.3.0-alltime-deepseek · 10353 in / 27068 out tokens · 263409 ms · 2026-08-03T10:17:01.897277+00:00 · methodology

0 comments

read the original abstract

We study a binary distributed hypothesis testing problem where two agents observe correlated binary vectors and communicate compressed information at the same rate to a central decision maker. In particular, we study linear compression schemes and show that simple truncation is the best linear scheme in two cases: (1) testing opposite signs of the same magnitude of correlation, and (2) testing for or against independence. We conjecture, supported by numerical evidence, that truncation is the best linear code for testing any correlations of opposite signs. Further, for testing against independence, we also compute classical random coding exponents and show that truncation, and consequently any linear code, is strictly suboptimal.

Figures

Figures reproduced from arXiv: 2601.10526 by Adway Girish, Emre Telatar, Robinson D. H. Cung.

**Figure 2.** Figure 2: (p0, p1)-plane where truncation is the best linear scheme for testing DSBS(p0) versus DSBS(p1): thick, black lines where it is known (Theorem 2) and red, shaded region where it is conjectured (Conjecture 1). than truncation and we are done. It is usually difficult to evaluate the exact type-I and type-II error probabilities of random codes, so we focus on the asymptotic Stein regime, as is common in the DH… view at source ↗

**Figure 3.** Figure 3: Comparison of Etr and EHan for (p0, p1) = (0.1, 0.9). Choosing PU|X and PV |Y to be the same BSC seems to be the best choice of test channels in Han’s scheme. At sufficiently large rates, EHan(R) > Etr(R), and hence we have an improved exponent Ecom(R) which is strictly better than Etr(R) at all R and strictly better than EHan(R) for small R. R, we require I(U; X) = 1 − h2(α) = R, where h2(a) denotes the e… view at source ↗

**Figure 4.** Figure 4: The hatched region contained between the two curves shows the [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

On The Most Discriminative Boolean Functions for Correlated Sources
cs.IT 2026-07 accept novelty 7.0

Level-k Boolean functions maximize KL divergence and Fisher information for unbiased pairs and identical pairs under nonnegative correlation, and minimize Bayes error in one-bit distributed hypothesis testing.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

Hypothesis testing with communication constraints

[AC86] R. Ahlswede and I. Csiszar. “Hypothesis testing with communication constraints”. In: IEEE Transactions on Information Theory32.4 (1986), pp. 533–542 (cit. on pp. 1, 2, 9). [Ber79] Toby Berger. “Decentralized estimation and decision theory”. In:IEEE Seven Springs Workshop on Information Theory. Vol

1986
[120]

Comparison of experiments

1979 (cit. on p. 1). [Bla51] David Blackwell. “Comparison of experiments”. In:Proc. Second Berkeley Symposium on Mathematical Statistics and Probability. 1951, pp. 93–102 (cit. on p. 3). [CK14] Thomas A. Courtade and Gowtham R. Kumar. “Which boolean functions maximize mutual information on noisy inputs?” In:IEEE Transactions on Information Theory 60.8 (20...

Pith/arXiv arXiv 1979

[1] [1]

Hypothesis testing with communication constraints

[AC86] R. Ahlswede and I. Csiszar. “Hypothesis testing with communication constraints”. In: IEEE Transactions on Information Theory32.4 (1986), pp. 533–542 (cit. on pp. 1, 2, 9). [Ber79] Toby Berger. “Decentralized estimation and decision theory”. In:IEEE Seven Springs Workshop on Information Theory. Vol

1986

[2] [120]

Comparison of experiments

1979 (cit. on p. 1). [Bla51] David Blackwell. “Comparison of experiments”. In:Proc. Second Berkeley Symposium on Mathematical Statistics and Probability. 1951, pp. 93–102 (cit. on p. 3). [CK14] Thomas A. Courtade and Gowtham R. Kumar. “Which boolean functions maximize mutual information on noisy inputs?” In:IEEE Transactions on Information Theory 60.8 (20...

Pith/arXiv arXiv 1979