Graphical models are a powerful framework used to succinctly represent high-dimensional distributions, and play a fundamental role in modern large-scale statistical inference. The graph underlying such a distribution specifies interactions between the variables, and explicitly captures the computational aspect inherent to statistical tasks. For unstructured settings such as those found in social networks, biology, and finance, a central problem is to determine a good model from observed data.

Learning graphical models from high-dimensional data is computationally challenging, and many different algorithms have been proposed over the years. Nevertheless, it is not clear what classes of models can be learned efficiently. In this talk we explore the problem from several angles and obtain a relatively unified view of what determines the computational complexity of learning graphical models. At the core of the approach lies a simple information-theoretic structural property of graphical models, which leads to efficient learning algorithms.