# Independence Testing for Bounded Degree Bayesian Network

arXiv: https://arxiv.org/abs/2204.08690 · HTML: https://mlsanity.com/paper/2204.08690/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 44 references that are in the map.
- First posted on arXiv 19 Apr 2022.

## Builds on (most cited first, 10 of 10)

- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Testing Product Distributions: A Closer Look](https://mlsanity.com/paper/2012.14632/) (2020)
- [Combinatorial Inference for Graphical Models](https://mlsanity.com/paper/1608.03045/) (2016)

## Built on by (most cited first, 5 of 5)

- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)

## Abstract (arXiv)

We study the following independence testing problem: given access to samples from a distribution P over 0,1n, decide whether P is a product distribution or whether it is varepsilon-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires exp(n) samples. We show in this work that if P has a sparse structure, then in fact only linearly many samples are required. Specifically, if P is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by d, then tildeTheta(2d/2· n/varepsilon2) samples are necessary and sufficient for independence testing.