  Bayes nets are extensively used in practice to efficiently represent joint
probability distributions over a set of random variables and capture dependency
relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given
a distribution $\mathbb{P}$, that is defined as the marginal distribution of a
Bayes net, it is $\mathsf{NP}$-hard to decide whether there is a
parameter-bounded Bayes net that represents $\mathbb{P}$. They called this
problem LEARN. In this work, we extend the $\mathsf{NP}$-hardness result of
LEARN and prove the $\mathsf{NP}$-hardness of a promise search variant of
LEARN, whereby the Bayes net in question is guaranteed to exist and one is
asked to find such a Bayes net. We complement our hardness result with a
positive result about the sample complexity that is sufficient to recover a
parameter-bounded Bayes net that is close (in TV distance) to a given
distribution $\mathbb{P}$, that is represented by some parameter-bounded Bayes
net, generalizing a degree-bounded sample complexity result of Brustle et al.
(EC 2020).
