Pith. sign in

REVIEW 1 major objections 4 minor 49 references

Testing (Conditional) Mutual Information

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Testing whether two discrete variables carry $\varepsilon$ mutual information costs, up to logarithmic factors, $\min\{d_A^{3/4}d_C^{1/4}/\varepsilon,\, d_A^{2/3}d_C^{1/3}/\varepsilon^{4/3}\}$ samples, and no tester can do better.

desk verdict The MI testing sample complexity is settled up to polylogs, and the CMI upper bound is a real advance; the load-bearing variance bound in the small-regime CMI tester checks out. read the letter →

arxiv 2506.03894 v1 pith:ELGOCJGX submitted 2025-06-04 cs.DS cs.ITmath.IT

Jan Seyfried , Sayantan Sen , Marco Tomamichel This is my paper
classification cs.DScs.ITmath.IT
keywords mutualinformationtestingconditionalsamplecomplexitydistributionequivalenceHellingerdistancecollision-basedestimatorindependence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper pins down how many independent samples are needed to test for mutual information: with $d_A \ge d_C$, the exact rate (up to logarithmic factors) is the smaller of $d_A^{3/4}d_C^{1/4}/\varepsilon$ and $d_A^{2/3}d_C^{1/3}/\varepsilon^{4/3}$, where $\varepsilon$ is the threshold of dependence to detect. This is the first sample-optimal mutual information tester: an upper bound built from reduction to equivalence testing in squared Hellinger distance, and a matching lower bound from a hard two-point construction. For the conditional version — testing whether $A$ and $C$ are independent given $B$, an operation at the core of causal discovery and Bayesian-network learning — the paper proves an upper bound with the same two-regime structure plus new symmetric terms, and matching lower bounds in several regimes. It conjectures the conditional bound is tight everywhere, and points to the exact spot where its lower bound falls short. The paper also contributes a collision-based sampler that fabricates reference-distribution samples in the hard regime of rare $B$-values, and an estimator robust to the resulting correlations, both presented as reusable tools.

What carries the argument

Everything runs through a single reduction chain. Mutual information (or conditional mutual information) is first converted to a testing problem in squared Hellinger distance, the distance that sums $(\sqrt{P}-\sqrt{Q})^2/2$ over outcomes, using the sandwich $D^2_H(P,Q) \le D(P\|Q) \le (2 + \log \max_i P(i)/Q(i))\, D^2_H(P,Q)$ after mixing the data with a little uniform noise so the reference distribution has no tiny atoms. The distribution is then partitioned into a two-dimensional grid of buckets (three-dimensional for CMI), each holding indices of nearly equal reference weight, which reduces Hellinger testing on each bucket to $\ell_2$ equivalence testing, the problem of deciding whether two unknown distributions are equal or far apart; the two legal ways to bound a bucket's $\ell_2$ norm, by $\sqrt{|S|}\cdot p_{\max}$ or by $\sqrt{p_{\max}}$, give the two competing regimes visible in all the exponents. For CMI the reference distribution $P_{A|B}P_{C|B}P_B$ cannot be sampled directly, so $B$ is split into a large regime, where a two-phase queue-based simulation yields exact reference samples, and a small regime, where reference samples are built from collisions among pairs sharing a rare $b$-value, producing correlated samples. Those correlated samples are handled by a new estimator $Z = \sum_i (X_iX'_i - 2X_iY_i + Y_iY'_i)$ over four independent sample sets, whose expectation is $\sum_i (E[X_i]-E[Y_i])^2$, exactly zero when the two processes coincide, and whose variance is controlled by the moment calculation in Lemma 7.9.

What would settle it

Take a small non-trivial case (e.g., $d_A = d_C = 2$, $d_B = 3$, $\varepsilon = 0.1$), implement SimABC and SimABCCI exactly as in Algorithms 4 and 5, and compare the empirical variance of $Z$ against the Lemma 7.9 bound $2\cdot 10^3(\|P^S_{ABC}\|_2^2+\|Q^S_{ABC}\|_2^2)\widetilde{N}_S^2$ across an adversarially chosen $P_{ABC}$ near the $\varepsilon$ threshold; exceeding the bound by a large factor would force the small-regime exponents up. For the mutual information claim, a direct simulation of the bucketed tester (Algorithm 2) at the crossover where $d_A^{3/4}d_C^{1/4}/\varepsilon$ meets $d_A^{2/3}d_C^{1/3}/\varepsilon^{4/3}$ would verify the second regime's $\varepsilon^{-4/3}$ dependence.

Watch

Extended reading notes

Core claim

Result 1: for mutual information testing with $d_A \ge d_C$, $\mathrm{SC}_{\mathrm{MI}}(\varepsilon, d_A, d_C) = \widetilde{\Theta}(\min\{d_A^{3/4}d_C^{1/4}/\varepsilon,\, d_A^{2/3}d_C^{1/3}/\varepsilon^{4/3}\})$. The upper bound comes from testing equivalence between the joint distribution $P_{AC}$ and a product reference $P_A P_C$ in squared Hellinger distance, refined by a two-dimensional bucketing that exploits the product structure; the lower bound uses a two-point construction over hard distributions and a new sharpened mutual-information inequality. Result 2: conditional mutual information testing obeys $\mathrm{SC}_{\mathrm{CMI}} = \widetilde{O}(\max\{f_{\mathrm{sym}}, f_{\mathrm{asym}}\})$, with $f_{\mathrm{sym}} = \max\{d_A^{1/2}d_B^{3/4}d_C^{1/2}/\varepsilon,\, \min\{d_A^{1/4}d_B^{7/8}d_C^{1/4}/\varepsilon,\, d_A^{2/7}d_B^{6/7}d_C^{2/7}/\varepsilon^{8/7}\}\}$ and $f_{\mathrm{asym}} = \min\{d_A^{3/4}d_B^{3/4}d_C^{1/4}/\varepsilon,\, d_A^{2/3}d_B^{2/3}d_C^{1/3}/\varepsilon^{4/3}\}$. Result 3 proves lower bounds matching in the asymmetric term and, for the symmetric term, in the case $d_A = d_C = 1$, leaving a gap the paper conjectures is only technical. A byproduct, the inequality $2I(X:A) \le \sum_a (\Pr[A=a|X=0]-\Pr[A=a|X=1])^2/(\Pr[A=a|X=0]+\Pr[A=a|X=1]) \le 12I(X:A)$, is claimed as new in its upper form and makes the lower-bound technique quantitatively tight.

Load-bearing premise

The small-regime CMI upper bound stands on the variance bound $\mathrm{Var}[Z] \le 2\cdot 10^3(\|P^S_{ABC}\|_2^2 + \|Q^S_{ABC}\|_2^2)\widetilde{N}_S^2$ for the new collision-based estimator (Lemma 7.9); if correlated samples from rare $b$-values concentrate any slower than this long moment calculation asserts, the claimed $d_B^{7/8}/\varepsilon$ and $d_B^{6/7}/\varepsilon^{8/7}$ sample counts would need to be larger.

Editorial extensions

If this is right

  • Mutual information can be detected with far fewer samples than learning the joint distribution: in the symmetric case the tight rate is $d^{3/4}/\varepsilon$ or $d^{2/3}/\varepsilon^{4/3}$, sublinear in the alphabet size, and the matching lower bound rules out any faster tester.
  • With unbalanced alphabets ($d_A \ge d_C$), the cost is $\min\{d_A^{3/4}d_C^{1/4}/\varepsilon,\, d_A^{2/3}d_C^{1/3}/\varepsilon^{4/3}\}$, so the smaller alphabet still matters through fractional powers and the crossover between regimes falls where the two expressions balance.
  • For CMI testing the bound separates into a symmetric term that grows with $B$ and an asymmetric term, exposing a $1/\varepsilon$ versus $1/\varepsilon^{8/7}$ tradeoff inside the symmetric term and a $d_B^{3/4}$ factor in the asymmetric term.
  • The new estimator, as a special case, reproduces optimal equivalence-testing bounds, $\Theta(b/\varepsilon^2)$ in $\ell_2$ and $O(nb/\varepsilon^2)$ in $\ell_1$, so the correlated-sample robustness costs nothing on ordinary i.i.d. data.
  • The sharpened two-sided inequality linking $I(X:A)$ to a $\chi^2$-style sum (Lemma 6.5) makes the lower-bound method quantitatively tight, which is what lets the MI lower bound match the upper bound up to polylog factors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The reduction chain (KL to Hellinger to bucketed $\ell_2$) is modular enough that the same architecture should transfer to testing other divergence-style measures, such as tolerant MI testing between thresholds $\varepsilon_1$ and $\varepsilon_2$, which the paper explicitly leaves open.
  • The collision sampler's bias, under which rare $b$-values appear with probability proportional to $p_b^2$ rather than $p_b$, is the real price of the small regime; an estimator that reweights collisions to unbias $P_B$ might shave the $d_B^{7/8}$ and $d_B^{6/7}$ exponents, a testable direction the paper does not pursue.
  • The explicit constants in the variance and covariance bounds ($2\cdot 10^3$ and the factor 123) invite a cheap numerical check on small alphabets before any downstream work builds on the small-regime tester.
  • Closing the symmetric CMI gap likely needs a three-variable hard construction where the $B$-alphabet is nontrivial but $d_A, d_C$ are still large, extending the two-type construction behind the MI lower bound.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper studies the sample complexity of testing whether two random variables are independent (I(A:C)=0) or have mutual information at least epsilon, and the conditional version for triples (A,B,C) with I(A:C|B)=0 versus at least epsilon. The main results are a polylog-optimal characterization of MI testing as Theta-tilde(min{d_A^{3/4} d_C^{1/4}/epsilon, d_A^{2/3} d_C^{1/3}/epsilon^{4/3}}) for d_A >= d_C (Result 1), an upper bound for CMI testing in terms of several regimes of alphabet sizes and epsilon (Result 2), and partial lower bounds for CMI testing (Result 3). The technical core is a reduction from KL/CMI testing to squared-Hellinger testing, a product-aware bucketing scheme for independence testing, a two-phase sampler that simulates the Markov-chain reference distribution in the large-p_b regime, and a collision-based sampler for the small-p_b regime whose outputs are only weakly correlated. The latter is analyzed through a new variance estimate for a correlation-robust equivalence-testing estimator.

Significance. If the lower-bound proof is repaired, Result 1 is the first sample-optimal MI tester (up to polylog factors) for arbitrary alphabet sizes, improving on prior O-tilde(d/epsilon) bounds. Result 2 gives a substantially better CMI upper bound than earlier work, and the partial lower bounds in Result 3 are honestly presented as a conjecture in the remaining regimes. The paper contains detailed proofs with explicit constants and algorithms, and the CMI upper bound's tightness is explicitly left as a conjecture rather than overclaimed. The proposed equivalence-testing estimator for correlated samples is a plausible contribution of independent interest. I checked the load-bearing variance bound Lemma 7.9 flagged in the review; the moment calculations in Appendix A.4 are consistent, and I do not find a concrete flaw there.

major comments (1)
  1. [§6.3, Lemma 6.12 and surrounding display] The proof of the lower bound contains an algebraic error that, as written, invalidates the claimed consequence. Lemma 6.12 asserts that d_A d_C^3 (epsilon n/(d_A d_C))^6 d_C/alpha <= O(1) implies n <= O(d_A^{5/6} d_C^{1/3}/(alpha epsilon)). Solving the inequality gives n <= O(d_A^{5/6} d_C^{1/3} alpha^{1/6}/epsilon); when alpha = n/d_A this becomes n <= O(d_A^{4/5} d_C^{2/5}/epsilon^{6/5}), not the displayed bound. As stated, the displayed bound can be strictly smaller than the advertised min in Eq. (148) for some parameter choices, so Theorem 6.1 does not follow from Lemmas 6.10 and 6.12 as written. The corrected bound appears to be large enough in the relevant parameter ranges, so I expect the claim is repairable, but the algebra and the final derivation in Eq. (148) need to be redone.
minor comments (4)
  1. [§2.2, Eq. (14)] The statement of Result 3 appears to have a typo: the displayed formula 'large-omega(f_sym(...), f_asym(...)})' is missing the enclosing max and has a stray brace. It should read Omega(max{f_sym(...), f_asym(...)}).
  2. [§9, Algorithm 9 and Theorem 9.1] The analysis of Algorithm 9 treats X_i, X'_i as independent Poi(N p_i) counts, but the algorithm splits an exactly-N-sample multiset into two halves. The paper should either state that the sample sizes are Poissonized first or add the standard Poissonization step, otherwise the displayed distributional identities are not justified as written.
  3. [§5.1, Lemma 5.5] The sample complexity in the lemma statement is O(sqrt(d) + 1/epsilon), while the proof derives O(sqrt(d + 1/epsilon^2)); these should be stated consistently and the equivalence justified.
  4. [§4, Theorem 4.2 and Algorithm 1] The symbol nu is used both for the mixing parameter nu = 2 eta - eta^2 and for the testing precision in Problem 6 and Theorem 4.2. Please disambiguate these two uses, for instance by renaming the mixing parameter.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivation chain is self-contained and anchored in external prior results; the sole self-citation ([TH18]) is contextual and appears in no proof.

full rationale

The derivation chain is self-contained and anchored in external prior work. The MI upper bound (Theorem 5.1) applies known equivalence-testing tools ([CDVV14, Thm. 2], [BFF+01, Thm. 12], [DK16]) to a two-dimensional bucketing of the product reference QAQC; the exponents in Result 1 follow from the two cases of the elementary Fact 3.3, not from any ansatz. The MI lower bound (Theorem 6.1) uses the DK16 mutual-information route with a new hard-instance construction; the matching exponents arise from solving the chi-squared-type bounds in Lemmas 6.10 and 6.12 for n under the subcases alpha = Theta(1) and alpha = n/dA, a mechanism different from the upper bound's Case 1/Case 2 split, so the match is genuine rather than forced. The CMI upper bound rests on the SimABC/SimABCCI sampler and the estimator Z = sum(XiX'i - 2XiYi + YiY'i), whose mean gap E[Z] = sum(E[Xi]-E[Yi])^2 (eq. 172) and variance bound (Lemma 7.9) are proved in Appendix A.4 by direct moment calculations under the stated small-regime assumption pb <= 1/NS; the sample complexity of Lemma 7.4 is obtained by solving Chebyshev's inequality for Ntilde_S, with the constants 4^7 and 2*10^3 absorbed analytically, not fitted. The CMI lower bound (Section 8) reduces to the MI lower bound and cites [CDKS18, Remark A.2] for one term. The only self-citation is [TH18], cited once in the introduction as application context and used in no proof, so it is not load-bearing. No fitted parameter is relabeled as a prediction; the thresholds in Algorithms 2, 6, 8, and 9 are set at half the proven mean gap of the respective estimators. The paper also honestly flags its own limitation ('We conjecture this to be tight in all regimes but our Result 3 only proves this partially'), which cuts against any disguised circularity. I find no step where a claimed result reduces, by the paper's own equations, to its inputs.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central bounds rest on standard distribution-testing tools and the paper's own technical lemmas. No new physical entities are introduced. The main external unproved input is the transformation of the CDKS18 TV lower bound into a CMI lower bound for the symmetric regime. Free parameters are analytical algorithm choices that affect only polylogarithmic factors and constants.

free parameters (4)
  • Mixing parameter eta (Algorithm 1) = ~O(epsilon^2 / (d_A d_C)^2)
    Chosen by hand to make Theorem 4.2 work: small enough that Lemma 4.1 preserves the epsilon gap, and to ensure the reference distribution's minimum probability mass is at least eta^2/(d_A d_C). This affects only polylogarithmic overhead.
  • Regime threshold nu (Algorithm 3) = 1/(2 N_S)
    Separates the small and large b regimes in CMI testing; ensures that b in B_S have expected count below 1, enabling the collision-based simulation. It sets the split between Lemma 7.4 and Lemma 7.10 sample complexities.
  • Bucket thresholds k_A, k_C, k_B, k_ABC = ceil(log(1/M)), ceil(log(1/M)), ceil(log(1/nu)), log^3(d_A d_B d_C / epsilon)
    Define the number of logarithmic weight categories in Algorithms 2 and 8. They are polylogarithmic and do not affect asymptotic exponents, but the central sample complexity statements are expressed through them (e.g., N_heavy, N_mixed).
  • Equivalence testing precision gamma and l2-norm bounds b = Equations (55)-(56) and (198)-(200)
    These are derived analytically to balance the two l2-norm bounds from Fact 3.3 in the bucketing analysis; they are not fitted to data.
assumptions (7)
  • standard math KL-Hellinger sandwich inequality: D_H^2(P,Q) <= D(P||Q) <= (2 + log(max_i P(i)/Q(i))) D_H^2(P,Q)
    Lemma 3.1 from [GS02] and [FO24], used in Theorem 4.2 to reduce (C)MI testing to squared Hellinger testing.
  • standard math Poissonization (Lemma 3.7) and Chernoff, Chebyshev, and Poisson concentration bounds (Lemmas 3.4, 3.5, 3.8)
    Used throughout for converting between sample counts and high-probability events.
  • standard math l2 equivalence testing with l2-norm bound: Theta(b/epsilon^2) samples suffice (Lemma 5.3, [CDVV14]) and the subset variant (Lemmas 5.5, 5.6, [DK16])
    Black-box subroutine for bucket-wise equivalence testing in Sections 5 and 7.
  • standard math Le Cam lower bound route via mutual information (Lemma 6.3, [DK16]) and the chi2-relating inequality (18)
    Framework for lower bounds in Section 6; the second inequality is proven in the paper as Lemma 6.5.
  • domain assumption Transfer of the CDKS18 TV-based lower bound to CMI (Remark A.2 in [CDKS18])
    Used for the symmetric term f_sym(epsilon, 1, d_B, 1) in Theorem 8.1; the conversion is cited, not reproduced.
  • domain assumption Problem setup: finite alphabets, i.i.d. sample access, promise gap with I=0 or I>=epsilon
    Defines Problems 1-4 and all sample complexity statements.
  • domain assumption Without loss of generality, d_A >= d_C due to symmetry between A and C
    Used throughout to present asymmetric exponents.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Testing (Conditional) Mutual Information." pith.science (2026). https://pith.science/paper/ELGOCJGX

@misc{pith2026250603894,
  author       = {Pith},
  title        = {Pith review of: Testing (Conditional) Mutual Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ELGOCJGX}},
  note         = {Machine review of arXiv:2506.03894}
}
abstract

We investigate the sample complexity of mutual information and conditional mutual information testing. For conditional mutual information testing, given access to independent samples of a triple of random variables $(A, B, C)$ with unknown distribution, we want to distinguish between two cases: (i) $A$ and $C$ are conditionally independent, i.e., $I(A\!:\!C|B) = 0$, and (ii) $A$ and $C$ are conditionally dependent, i.e., $I(A\!:\!C|B) \geq \varepsilon$ for some threshold $\varepsilon$. We establish an upper bound on the number of samples required to distinguish between the two cases with high confidence, as a function of $\varepsilon$ and the three alphabet sizes. We conjecture that our bound is tight and show that this is indeed the case in several parameter regimes. For the special case of mutual information testing (when $B$ is trivial), we establish the necessary and sufficient number of samples required up to polylogarithmic terms. Our technical contributions include a novel method to efficiently simulate weakly correlated samples from the conditionally independent distribution $P_{A|B} P_{C|B} P_B$ given access to samples from an unknown distribution $P_{ABC}$, and a new estimator for equivalence testing that can handle such correlated samples, which might be of independent interest.

Figures

Figures reproduced from arXiv: 2506.03894 by the authors.

Figure 1
Figure 1. Partition of dA × dC based on QˆA and QˆC. Indices (a, c) of similar weight qˆaqˆc are grouped together in buckets Sij , which are used to perform piecewise equivalence testing with PAC. The axes are labeled according to the corresponding category, which is inverse logarithmic to the weight of the probabilities. The color of the categories indicate a different analysis of the sample complexity of the categories. The… view at source ↗
Figure 2
Figure 2. Partition of dA × dB × dC based on PˆAB, PˆBC, and PˆB. Indices (a, b, c) of similar weight pˆabpˆbc/pˆb are grouped together in categories L k ij , which are used to perform piecewise equivalence testing with PABC. The axes are labeled according to the corresponding category, which is inverse logarithmic to the weight of the probabilities. The color of the categories indicate a different analysis of the sample comp… view at source ↗
Figure 3
Figure 3. (Comparison of sampling methods). In the large regim [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Partition of dA × dC based on QˆA and QˆC. Indices (a, c) of similar weight qˆaqˆc are grouped together in categories Sij , which are used to perform piecewise equivalence testing with PAC. The axes are labeled according to the corresponding category, which is inverse …
Figure 5
Figure 5. Figure 5: Partition of dA × dB × dC based on PˆAB, PˆBC, and PˆB. Indices (a, b, c) of similar weight pˆabpˆbc/pˆb are grouped together in categories L k ij , which are used to perform piecewise equivalence testing with PABC. The axes are labeled according to the corresponding c…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

49 extracted references · 42 canonical work pages

  1. [1]

    Optimal testing for properties of distributions

    Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems , 28, 2015

    2015

  2. [2]

    Sublinear algorithms for outlier detection and generalized closeness testing

    Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Sublinear algorithms for outlier detection and generalized closeness testing. In 2014 IEEE International Symposium on Information Theory , pages 3200--3204. IEEE, 2014

    work page 2014

  3. [3]

    T. Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science , pages 442--451. IEEE , 2001

    work page 2001

  4. [4]

    Testing closeness of discrete distributions

    Tu g kan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM) , 60(1):1--25, 2013

    work page 2013

  5. [5]

    Near-optimal learning of tree-structured distributions by chow and liu

    Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent YF Tan, and NV Vinodchandran. Near-optimal learning of tree-structured distributions by chow and liu. SIAM Journal on Computing , 52(3):761--793, 2023

    work page 2023

  6. [6]

    Testing closeness with unequal sized samples

    Bhaswar Bhattacharya and Gregory Valiant. Testing closeness with unequal sized samples. Advances in Neural Information Processing Systems , 28, 2015

    work page 2015

  7. [7]

    A survey on distribution testing: Your data is big

    Cl \'e ment L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing , pages 1--100, 2020

    work page 2020

  8. [8]

    Topics and techniques in distribution testing: A biased but representative sample

    Cl \'e ment L Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory , 19(6):1032--1198, 2022

    work page 2022

Show all 49 references
  1. [9]

    Testing conditional independence of discrete distributions

    Cl \'e ment L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing conditional independence of discrete distributions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 735--748, 2018

    2018

  2. [10]

    Testing bayesian networks

    Cl \'e ment L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing bayesian networks. IEEE Transactions on Information Theory , 66(5):3132--3170, 2020

    2020

  3. [11]

    Optimal algorithms for testing closeness of discrete distributions

    Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1193--1203. SIAM, 2014

    2014

  4. [12]

    Canonne, Ayush Jain, Gautam Kamath, and Jerry Li

    Cl \' e ment L. Canonne, Ayush Jain, Gautam Kamath, and Jerry Li. The price of tolerance in distribution testing. In COLT , volume 178 of Proceedings of Machine Learning Research , pages 573--624. PMLR , 2022

    2022

  5. [13]

    Approximating discrete probability distributions with dependence trees

    CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory , 14(3):462--467, 1968

    1968

  6. [14]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing) . Wiley-Interscience, USA, 2006

    2006

  7. [15]

    Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, and Cl \' e ment L. Canonne. Learning bounded-degree polytrees with known skeleton. In Claire Vernade and Daniel Hsu, editors, International Conference on Algorithmic Learning Theory, 25-28 February 2024, La Jolla, California, ...

    2024

  8. [16]

    Optimal testing of discrete distributions with high probability

    Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, John Peebles, and Eric Price. Optimal testing of discrete distributions with high probability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 542--555, 2021

    2021

  9. [17]

    Collision-based testers are optimal for uniformity and closeness

    Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. Chic. J. Theor. Comput. Sci , 25:1--21, 2019

    2019

  10. [18]

    A new approach for testing properties of discrete distributions

    Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 685--694. IEEE, 2016

    2016

  11. [19]

    Which distribution distances are sublinearly testable? In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '18, page 2747–2764, USA, 2018

    Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution distances are sublinearly testable? In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '18, page 2747–2764, USA, 2018. Society for Industrial and Applied Mathematics

    2018

  12. [20]

    Bayesian test of significance for conditional independence: the multinomial model

    Pablo de Morais Andrade, Julio Michael Stern, and Carlos Alberto de Bragan c a Pereira. Bayesian test of significance for conditional independence: the multinomial model. Entropy , 16(3):1376--1395, 2014

    2014

  13. [21]

    Dubhashi and A

    D.P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algoritms . In Cambridge University Press , 2009

    2009

  14. [22]

    Square hellinger subadditivity for bayesian networks and its applications to identity testing

    Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. In Conference on Learning Theory , pages 697--703. PMLR, 2017

    2017

  15. [23]

    Sample-optimal and efficient learning of tree ising models

    Constantinos Daskalakis and Qinxuan Pan. Sample-optimal and efficient learning of tree ising models. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1...

    2021

  16. [24]

    Quantum chi-squared tomography and mutual information testing

    Steven T Flammia and Ryan O'Donnell. Quantum chi-squared tomography and mutual information testing. Quantum , 8:1381, 2024

    2024

  17. [25]

    Introduction to property testing

    Oded Goldreich. Introduction to property testing . Cambridge University Press, 2017

    2017

  18. [26]

    Testing for causality: A personal viewpoint

    Clive WJ Granger. Testing for causality: A personal viewpoint. Journal of Economic Dynamics and control , 2:329--352, 1980

    1980

  19. [27]

    Gibbs and Francis Edward Su

    Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International Statistical Review / Revue Internationale de Statistique , 70(3):419--435, 2002

    2002

  20. [28]

    Local permutation tests for conditional independence

    Ilmun Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Local permutation tests for conditional independence. The Annals of Statistics , 50(6):3388--3414, 2022

    2022

  21. [29]

    Conditional independence testing for discrete distributions: Beyond x 2-and g-tests

    Ilmun Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Conditional independence testing for discrete distributions: Beyond x 2-and g-tests. Electronic Journal of Statistics , 18(2):4767--4794, 2024

    2024

  22. [30]

    Testing properties of collections of distributions

    Reut Levi, Dana Ron, and Ronitt Rubinfeld. Testing properties of collections of distributions. Theory of Computing , 9(1):295--347, 2013

    2013

  23. [31]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

    1995

  24. [32]

    Testing conditional independence on discrete data using stochastic complexity

    Alexander Marx and Jilles Vreeken. Testing conditional independence on discrete data using stochastic complexity. In The 22nd International Conference on Artificial Intelligence and Statistics , pages 496--505. PMLR, 2019

    2019

  25. [33]

    Learning bayesian networks , volume 38

    Richard E Neapolitan et al. Learning bayesian networks , volume 38. Pearson Prentice Hall Upper Saddle River, 2004

    2004

  26. [34]

    Minimax optimal conditional independence testing

    Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimal conditional independence testing. The Annals of Statistics , 49(4):2151--2177, 2021

    2021

  27. [35]

    Probabilistic reasoning in intelligent systems: networks of plausible inference

    Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference . Elsevier, 2014

    2014

  28. [36]

    Taming big probability distributions

    Ronitt Rubinfeld. Taming big probability distributions. XRDS: Crossroads, The ACM Magazine for Students , 19(1):24--28, 2012

    2012

  29. [37]

    Causation, prediction, and search

    Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search . MIT press, 2001

    2001

  30. [38]

    C. Shannon. A mathematical theory of communication. Bell System Technical Journal , 27:379--423, 1948

    1948

  31. [39]

    Operational interpretation of rényi information measures via composite hypothesis testing against product and markov distributions

    Marco Tomamichel and Masahito Hayashi. Operational interpretation of rényi information measures via composite hypothesis testing against product and markov distributions. IEEE Transactions on Information Theory , 64:1064--1082, 2 2018

    2018

  32. [40]

    Some bounds for the logarithmic function

    Flemming Topsoe. Some bounds for the logarithmic function. Inequality Theory and Applications , 4, 01 2007

    2007

  33. [41]

    Testing symmetric properties of distributions

    Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing , 40(6):1927--1968, 2011

    1927

  34. [42]

    Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts

    Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 685--694, 2011

    2011

  35. [43]

    The power of linear estimators

    Gregory Valiant and Paul Valiant. The power of linear estimators. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages 403--412. IEEE, 2011

    2011

  36. [44]

    Optimal estimation of gaussian (poly)trees

    Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, and Arnab Bhattacharyya. Optimal estimation of gaussian (poly)trees. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, International Conference on Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congre...

    2024

  37. [45]

    Characteristic function based testing for conditional independence: A nonparametric regression approach

    Xia Wang and Yongmiao Hong. Characteristic function based testing for conditional independence: A nonparametric regression approach. Econometric Theory , 34(4):815--849, 2018

    2018

  38. [46]

    Minimax rates of entropy estimation on large alphabets via best polynomial approximation

    Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory , 62(6):3702--3720, 2016

    2016

  39. [47]

    Chebyshev polynomials, moment matching, and optimal estimation of the unseen

    Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics , 47(2):857--883, 2019

    2019

  40. [48]

    A. D. Wyner. A definition of conditional mutual information for arbitrary ensembles. Information and Control , 38:51--59, 7 1978

    1978

  41. [49]

    Kernel-based conditional independence test and application in causal discovery

    K Zhang, J Peters, D Janzing, and B Sch \"o lkopf. Kernel-based conditional independence test and application in causal discovery. In 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011) , pages 804--813. AUAI Press, 2011

    2011

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.