Not all FPRASs are equal: demystifying FPRASs for DNF-counting

DOI10.1007/S10601-018-9301-XMaRDI QIDQ2009190zbMATH OpenOpenAlexWikidataFDO

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

Publication date 27 November 2019

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10601-018-9301-x

zbMATH Keywords

Boolean formulasdisjunctive normal formfully polynomial randomized approximation schemehashingmodel counting

Mathematics Subject Classification ID

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

Recommendations

• On hashing-based approaches to approximate DNF-counting
• DNF sparsification and a faster deterministic counting algorithm
• scientific article; zbMATH DE number 1315584
• Theory and Applications of Satisfiability Testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• An Optimal Algorithm for Monte Carlo Estimation
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• DNF sparsification and a faster deterministic counting algorithm
• Improved pseudorandom generators for depth 2 circuits
• Monte-Carlo approximation algorithms for enumeration problems
• Oblivious bounds on the probability of boolean functions
• On deterministic approximation of DNF
• On hashing-based approaches to approximate DNF-counting
• Pseudorandom bits for constant depth circuits
• Scalable approximation of quantitative information flow in programs
• The Complexity of Enumeration and Reliability Problems

Cited in

(7)

• Enumerating models of DNF faster: breaking the dependency on the formula size
• DNF sparsification and a faster deterministic counting algorithm
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• On hashing-based approaches to approximate DNF-counting
• Model counting meets \(F_0\) estimation
• Hashing-based approximate counting of minimal unsatisfiable subsets
• Approximating Klee's measure problem and a lower bound for union volume estimation

Describes a project that uses

Uses Software

• M4RI
• sharpSAT
• MayBMS

This page was built for publication: Not all FPRASs are equal: demystifying FPRASs for DNF-counting

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