Paper Info
Title
Oblivious bounds on the probability of boolean functions
Abstract
This article develops upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach dissociation and give an exact characterization of optimal oblivious bounds, that is, when the new probabilities are chosen independently of the probabilities of all other variables. Our motivation comes from the weighted model counting problem (or, equivalently, the problem of computing the probability of a Boolean function), which is #P-hard in general. By performing several dissociations, one can transform a Boolean formula whose probability is difficult to compute into one whose probability is easy to compute, and which is guaranteed to provide an upper or lower bound on the probability of the original formula by choosing appropriate probabilities for the dissociated variables. Our new bounds shed light on the connection between previous relaxation-based and model-based approximations and unify them as concrete choices in a larger design space. We also show how our theory allows a standard relational database management system (DBMS) to both upper and lower bound hard probabilistic queries in guaranteed polynomial time.
Year
DOI
Venue
2014
10.1145/2532641
ACM Transactions on Database Systems (TODS)
Keywords
DocType
Volume
new bound,new individual probability,lower bound hard probabilistic,optimal oblivious bound,appropriate probability,lower bound,guaranteed polynomial time,new probability,boolean function,boolean formula
Journal
abs/1409.6052
Issue
ISSN
Citations 
1
Pre-print for ACM Transactions on Database Systems, January 2014, Vol 39, No 1, Article 5
6
PageRank 
References 
Authors
0.40
32
2
Name
Order
Citations
PageRank
Wolfgang Gatterbauer149834.18
Dan Suciu296251349.54