Oblivious bounds on the probability of boolean functions
From MaRDI portal
Publication:2943565
DOI10.1145/2532641zbMATH Open1321.68246OpenAlexW3122109288MaRDI QIDQ2943565FDOQ2943565
Abstract: This paper 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, i.e. when the new probabilities are chosen independent 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.
Recommendations
- scientific article; zbMATH DE number 176875
- Probabilities of Boolean functions given by random implicational formulas
- Probabilistic estimation of the algebraic degree of Boolean functions
- scientific article; zbMATH DE number 7768387
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- Minimizability of random Boolean functions
- scientific article; zbMATH DE number 4025337
- On the complexity of computing a random Boolean function over the reals
- Complexity and Probability of Some Boolean Formulas
- On the Probabilistic Degrees of Symmetric Boolean Functions
Cites work
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 3126031 (Why is no real title available?)
- scientific article; zbMATH DE number 1946853 (Why is no real title available?)
- A Scheme for Fast Parallel Communication
- Manipulating MDD relaxations for combinatorial optimization
- Mini-buckets: a general scheme for bounded inference
- Oblivious bounds on the probability of boolean functions
- On probabilistic inference by weighted model counting
- On the power of clause-learning SAT solvers as resolution engines
- Optimization Bounds from Binary Decision Diagrams
- Probabilistic Horn abduction and Bayesian networks
- Relax, compensate and then recover: a theory of anytime, approximate inference
- SampleSearch: importance sampling in presence of determinism
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The complexity of computing the permanent
Cited in
(5)- scientific article; zbMATH DE number 1796950 (Why is no real title available?)
- Tight Bounds on Oblivious Chaining
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Oblivious bounds on the probability of boolean functions
- Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
This page was built for publication: Oblivious bounds on the probability of boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943565)
