A Caltech Library Service

Complexity of Inference in Graphical Models

Chandrasekaran, Venkat and Srebro, Nathan and Harsha, Prahladh (2008) Complexity of Inference in Graphical Models. In: 24th Conference on Uncertainty in Artificial Intelligence and Statistics. AUAI Press , Corvallis, OR, pp. 70-78. ISBN 0974903949.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with un- bounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemTechnical Report Paper
Additional Information:We would like to thank Lance Fortnow and Jaikumar Radhakrishnan for helpful discussions and referring us to (Tamassia & Tollis, 1989).
Record Number:CaltechAUTHORS:20121008-154959981
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34765
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 22:58
Last Modified:02 Jun 2023 00:14

Repository Staff Only: item control page