Oblivious bounds on the probability of boolean functions

DOI10.1145/2532641zbMath1321.68246arXiv1409.6052OpenAlexW3122109288MaRDI QIDQ2943565

Wolfgang Gatterbauer, Dan Suciu

Publication date: 3 September 2015

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

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

zbMATH Keywords

relaxationBoolean expressionsprobabilistic databasesweighted model countingoblivious approximations

Mathematics Subject Classification ID

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

Related Items (3)

Oblivious bounds on the probability of boolean functions ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Decision Diagram Decomposition for Quadratically Constrained Binary Optimization

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of clause-learning SAT solvers as resolution engines
• SampleSearch: importance sampling in presence of determinism
• The complexity of computing the permanent
• Probabilistic Horn abduction and Bayesian networks
• On probabilistic inference by weighted model counting
• Oblivious bounds on the probability of boolean functions
• Optimization Bounds from Binary Decision Diagrams
• Manipulating MDD Relaxations for Combinatorial Optimization
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Mini-buckets
• A Scheme for Fast Parallel Communication
• Relax, Compensate and Then Recover: A Theory of Anytime, Approximate Inference

This page was built for publication: Oblivious bounds on the probability of boolean functions