Projects
Optimal Sample Complexity Lower Bounds on Conditional Independence Testing
05/2026 · Joint work with Neelkanth Mishra, Sayantan Sen, and Marco Tomamichel
We resolve the remaining open questions in the sample complexities of both conditional independence testing and conditional mutual information testing in discrete distributions, up to logarithmic factors. To do this, we generalize the lower bound constructions by Canonne, Diakonikolas, Kane, and Stewart (STOC 2018).
[Accepted for presentation at COLT 2026]
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]