Stochastic Systems Group  

Complexity of Inference in Graphical Models
Venkat Chandrasekaran
SSG, MIT
We consider the complexity of inference in a graphical model consisting of discretevalued variables as a function of the treewidth of the underlying graph. It is wellknown that the worstcase instance of this problem is NPhard. We discuss the complexity of "bestcase" instances of this problem and show that inference is still superpolynomial in the treewidth. In other words for any sequence of graphs indexed by treewidth, inference is superpolynomial 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 jonesb@mit.edu