Paper Info
Title
New Limits for Knowledge Compilation and Applications to Exact Model Counting
Abstract
We show new limits on the efficiency of using current techniques to make exact probabilistic inference for large classes of natural problems. In particular we show new lower bounds on knowledge compilation to SDD and DNNF forms. We give strong lower bounds on the complexity of SDD representations by relating SDD size to best-partition communication complexity. We use this relationship to prove exponential lower bounds on the SDD size for representing a large class of problems that occur naturally as queries over probabilistic databases. A consequence is that for representing unions of conjunctive queries, SDDs are not qualitatively more concise than OBDDs. We also derive simple examples for which SDDs must be exponentially less concise than FBDDs. Finally, we derive exponential lower bounds on the sizes of DNNF representations using a new quasipolynomial simulation of DNNFs by nondeterministic FBDDs.
Year
Venue
Field
2015
International Conference on Uncertainty in Artificial Intelligence
Conjunctive query,Exponential function,Nondeterministic algorithm,Computer science,Algorithm,Communication complexity,Knowledge compilation,Probabilistic logic,Model counting,Exponential growth
DocType
Volume
ISBN
Journal
abs/1506.02639
978-0-9966431-0-8
Citations 
PageRank 
References 
5
0.45
11
Authors
2
Name
Order
Citations
PageRank
Paul Beame12234176.07
Vincent Liew271.16