On hashing-based approaches to approximate DNF-counting

DOI10.4230/LIPICS.FSTTCS.2017.41MaRDI QIDQ5136333zbMATH OpenFDO

Authors Kuldeep S. Meel, Aditya A. Shrotri, Moshe Y. Vardi

Publication date 25 November 2020

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

zbMATH Keywords

approximationmodel countinghash functionsDNF

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Not all FPRASs are equal: demystifying FPRASs for DNF-counting
• A new probabilistic algorithm for approximate model counting
• Theory and Applications of Satisfiability Testing
• Two approximate algorithms for model counting
• Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling

Cites work

• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 1888461 (Why is no real title available?)
• scientific article; zbMATH DE number 2243356 (Why is no real title available?)
• An Optimal Algorithm for Monte Carlo Estimation
• Model counting: a new stategy for obtaining good bounds
• Monte-Carlo approximation algorithms for enumeration problems
• On computing minimal independent support and its applications to sampling and counting
• On the hardness of approximate reasoning
• Probabilistic planning via heuristic forward search and weighted model counting
• Random generation of combinatorial structures from a uniform distribution
• Short XORs for Model Counting: From Theory to Practice
• The Complexity of Enumeration and Reliability Problems

Cited in

(8)

• Not all FPRASs are equal: demystifying FPRASs for DNF-counting
• IASCAR: incremental answer set counting by anytime refinement
• A new probabilistic algorithm for approximate model counting
• Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
• Model counting meets \(F_0\) estimation
• Approximate weighted model integration on DNF structures
• Open-world probabilistic databases: semantics, algorithms, complexity
• Rounding meets approximate model counting

This page was built for publication: On hashing-based approaches to approximate DNF-counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136333)