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]