CS Paper Radar

Distributed Hypothesis Testing Against Dependence

Han Wu, Shun Watanabe

cs.IT ·submitted 2026-08-25 11:06 UTC · v2

Abstract

We study distributed hypothesis testing and establish the exact error exponent in single-letter form for new testing problems. In distributed hypothesis testing, a receiver decides between $\mathcal{H}_0:P_{XY}$ and $\mathcal{H}_1:Q_{XY}$ based on $Y^n$ and a rate-limited description of $X^n$. So far, such single-letter forms are known only for testing against independence, studied by Ahlswede and Csiszár, and testing against conditional independence, studied by Rahman and Wagner. In this paper, we study testing against dependence, where $P_{XY}=P_XP_Y$, and show that its error exponent is given by Han's exponent, which is established by single-letterizing a multi-letter version of Han's exponent. We also disprove a previous conjecture of Han claiming that the error exponent is given by the lautum information, as we show that Han's exponent can strictly exceed the latter. We then consider the Cartesian product of testing against dependence and testing against independence, and derive a single-letter characterization of its error exponent. We next study testing against conditional dependence, which is the dependence-testing counterpart of the setting studied by Rahman and Wagner. We derive a single-letter converse bound for the error exponent by introducing and solving a related setting where the side information is also available to the transmitter. We show that our converse bound is tight in some cases by using a conditional-coding version of the quantization scheme. Finally, we extend our converse method for testing against dependence to the general setting, and recover a recently established single-letter converse bound.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Rate Exponent Tradeoff for New Classes of Distributed Hypothesis Testing Problems

cs.IT ·2026-08-24 ·Zhenduo Wen, Amin Gohari, Michèle Wigger
theory similarity 0.66
Abstract

We study the optimal Stein error exponent for one-way distributed hypothesis testing under a communication rate constraint. We establish exact rate-exponent tradeoffs for new classes of finite-alphabet sources, including a complete single-letter characterization for every pair of strictly positive binary joint distributions as well as testing-against-dependence. Our converse analysis refines the auxiliary-receiver method through three complementary steps. First, we establish an information-projection identity that identifies the posterior-divergence optimization in an existing converse with Han's exponent functional. Second, we obtain an additional excess-rate branch by retaining a mutual-information term discarded in the usual rate relaxation. Third, we develop a two-telescope upper bound whose auxiliary variables are coupled through a joint rate constraint. Combining these bounds with information-geometric matching conditions yields exact exponents for three classes of sources by matching the achievable bounds of Han and Shimokawa-Han-Amari.

0.37

Distributed Quantum Property Testing with Quantum Carrier Pigeons

cs.DS quant-ph ·2026-09-08 ·Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa
theory similarity 0.59
Abstract · Merges and subsumes arXiv:2604.05962 and arXiv:2606.31753, and includes additional/improved results. 67 pages, 1 figure, 1 table

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

0.45

Convex splitting by binary quantum hypothesis testing

cs.IT quant-ph ·2026-11-19 ·Mark M. Wilde
similarity 0.58
Abstract · 44 pages, 4 figures

How many independent quantum systems does it take to hide one system that is correlated with a reference? An observer can measure all the systems together with the reference to detect the correlation. We turn any such measurement into binary tests on a single system and the reference. For each test we bound the probability of declaring a signal when an independent pair was prepared. Averaging the largest signal acceptance probabilities allowed by these bounds controls the normalized trace distance in the convex-split lemma. A second bound gives a sufficient number of systems by minimizing the hypothesis-testing relative entropy over the state of the reference. Both bounds hold for density operators on separable Hilbert spaces. Comparing two distributions for the location of the hidden system gives one-shot bounds for private communication and one-way secret key distillation, including the public information available to an eavesdropper. For a fixed finite-alphabet model with separable quantum outputs and positive information advantage and variances, we recover the known Gaussian corrections to the attainable number of private or key bits from $n$ independent repetitions and bound the remaining loss by $\log_2 n+O(1)$ at fixed errors. The position-based key distillation protocol attains this bound with $O(n)$ public bits.

0.37

Near-Optimal Mixedness Testing with Pauli Measurements

cs.CC quant-phcs.IT ·2026-08-19 ·Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu
theory similarity 0.57
Abstract · Added determinstic Pauli mixedness testing results, fixed typos

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task with simple single-qubit measurements, i.e. measurements that are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness testing by showing that its copy-complexity is $\tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

0.31

Embedding-Bias in Conditional Independence Testing

cs.LG stat.ML ·2026-10-08 ·Nikolaj Thams, Anton Rask Lundborg
similarity 0.57
Abstract

To test conditional independence of $X$ and $Y$ given a text or an image $Z$, one conditions on an embedding $ψ(Z)$ in place of $Z$. The embedded test is valid if $Z$ is independent of $X$ or of $Y$ given $ψ(Z)$, which cannot be confirmed from data, and when this fails, the rejection probability under the null hypothesis can tend to one. We study this failure, and show that focusing on a specific form of dependence relaxes what the embedding must retain. For a residual correlation test inspired by the Generalised Covariance Measure, validity only requires that the parts of $\mathbb{E}[X \mid Z]$ and $\mathbb{E}[Y \mid Z]$ missed by $\mathbb{E}[X \mid ψ(Z)]$ and $\mathbb{E}[Y \mid ψ(Z)]$ are uncorrelated. Otherwise, we treat the discarded information as an omitted variable. Under the null hypothesis, the bias equals the absolute correlation of the missed parts times the geometric mean of two partial $R^2$ values. This identity yields a robust test valid under a declared tolerance for the geometric mean, which, like a sensitivity parameter, is not identified from the data. On synthetic data and text embeddings, the robust test holds its level approximately. On text generated by a language model, under an exact null hypothesis, every embedding, even the generator's own states, biases the embedded test.

0.20

Asymmetric Likelihood-Free Hypothesis Testing

cs.LG cs.DScs.ITmath.ST+1 ·2026-10-21 ·Gunjan Kumar, Yash Pote, Jonathan Scarlett
similarity 0.56
Abstract

In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the goal is to identify whether $D=P$ or $D=Q$. We study asymmetric likelihood-free hypothesis testing, where the sample budgets $s_P$ and $s_Q$ for $P$ and $Q$ may differ, and characterize the feasible triples $(s_P,s_Q,s_D)$ up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, $n$ samples from $P$ and $n^{3/4}$ from $Q$ allow testing with $\widetilde O(n^{1/4})$ samples from $D$, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require $Ω(\sqrt n)$ samples from $D$. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among $k$ distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of $\widetildeΘ(k^{1/4})$.

0.25

Embedded Conditional Independence Tests for Large Language Model Generated Text with an Application to German Parliament Speeches

cs.AI stat.MLcs.LGmath.ST+1 ·2026-09-01 ·Marco Simnacher, Georg Keilbar, Benjamin König, Christoph Lippert, Sonja Greven
similarity 0.56
Abstract · 41 pages, 6 figures

Conditional independence tests (CITs) test for conditional dependence between two random objects $X$ and $Y$ given a third random object $Z$. Existing CITs have limited applicability to high-dimensional data, especially multimodal data like text. However, we show that such tests are of interest for large language model (LLM) outputs, where we test whether an output $X$ generated from a source text $Z$ carries information about an attribute $Y$ beyond $Z$ itself. For this purpose, we propose embedded CITs (eCITs), which embed $X$ and $Z$ and apply an existing CIT to the resulting representations and to $Y$. We show that, provided the embedding of $Z$ is sufficient, i.e. retains the information $Z$ carries about either $Y$ or the representation of $X$, the null hypothesis transfers from $X$ and $Z$ to their representations, so that a CIT valid for the embedded hypothesis is valid for the original one. We further give conditions for equivalence of the two hypotheses, and show that sufficiency weakens to mean sufficiency when the embedded test targets conditional mean independence. We propose a semi-synthetic simulation design to assess type I error (T1E) control and power of the eCITs for given embedding maps on a specific dataset and task, and use it to evaluate them on our application. Applying the eCITs to German Parliament speeches, we find for all combinations of embedding maps considered that the summaries of two LLMs contain information about the speaker's faction and gender beyond the speech they were generated from.

0.48

On the Limits of Quantum Multiparty Simultaneous Communication

cs.CC quant-ph ·2026-09-09 ·Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
theory similarity 0.55
Abstract · 27 pages, 1 figure

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

0.25