Extended View on Large-Sample Learning of Bayesian Networks

In this talk we will consider one of the main complexity results in the field of Bayesian networks: the NP-hardness of so called large-sample Bayesian network learning (D. M. Chickering, D. Heckerman, and C. Meek. "Large-Sample Learning of Bayesian Networks is NP-Hard". Journal of Machine Learning Research, 5:1287–1330, 2004). We will present the background, motivation and statement of the considered problem.
Then we will show how this result can be extended. We will introduce a significantly new formulation of the problem standing in the interesting complementary relation with the original one - which turns out to be NP-hard too.