Oblivious bounds on the probability of boolean functions

DOI10.1145/2532641zbMATH Open1321.68246arXiv1409.6052OpenAlexW3122109288MaRDI QIDQ2943565FDOQ2943565

Authors: Wolfgang Gatterbauer, Dan Suciu 

Publication date: 3 September 2015

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1409.6052

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

zbMATH Keywords

relaxationprobabilistic databasesBoolean expressionsweighted model countingoblivious approximations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cites Work

• The complexity of computing the permanent
• Manipulating MDD relaxations for combinatorial optimization
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Title not available (Why is that?)
• Title not available (Why is that?)
• On probabilistic inference by weighted model counting
• Title not available (Why is that?)
• Mini-buckets: a general scheme for bounded inference
• Probabilistic Horn abduction and Bayesian networks
• Optimization Bounds from Binary Decision Diagrams
• SampleSearch: importance sampling in presence of determinism
• On the power of clause-learning SAT solvers as resolution engines
• A Scheme for Fast Parallel Communication
• Oblivious bounds on the probability of boolean functions
• Relax, compensate and then recover: a theory of anytime, approximate inference

Cited In (5)

• Not all FPRASs are equal: demystifying FPRASs for DNF-counting
• Oblivious bounds on the probability of boolean functions
• Tight Bounds on Oblivious Chaining
• Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
• Title not available (Why is that?)

Uses Software

• JBool

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)