Independence Testing for Bounded Degree Bayesian Networks

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.