|Stochastic Systems Group|
Complexity of Inference in Graphical Models
We consider the complexity of inference in a graphical model consisting of discrete-valued variables as a function of the treewidth of the underlying graph. It is well-known that the worst-case instance of this problem is NP-hard. We discuss the complexity of "best-case" instances of this problem and show that inference is still super-polynomial in the treewidth. In other words for any sequence of graphs indexed by treewidth, inference is super-polynomial in the treewidth (given freedom in choosing the potentials on the nodes and edges of the graphs). Our analysis is based on various results and hypotheses from complexity theory and graph minor theory.
Joint work with Nathan Srebro and Prahladh Harsha.
Problems with this site should be emailed to firstname.lastname@example.org