CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20121008-154959981

[img]
Preview
PDF - Submitted Version
See Usage Policy.

220kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20121008-154959981

Abstract

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
http://resolver.caltech.edu/CaltechAUTHORS:20121011-133225017Related ItemTechnical Report
https://arxiv.org/abs/1206.3240arXivDiscussion 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:https://resolver.caltech.edu/CaltechAUTHORS:20121008-154959981
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34765
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Oct 2012 22:58
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page