Testing (Conditional) Mutual Information

05/2025 · Joint work with Sayantan Sen and Marco Tomamichel
We prove tight bounds on the sample complexity of mutual information testing and upper bounds on the sample complexity of conditional mutual information testing, both for discrete distributions. The underlying idea is a reduction to equivalence testing in Hilbert-Schmidt distance (see Diakonikolas and Kane (FOCS 2016)) between the original distribution and simulated samples of a (conditionally) independent version of the given distribution.
[COLT 2025] [arXiv]