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

DOI10.1007/s10601-018-9301-xzbMath1483.68498OpenAlexW2906587736MaRDI QIDQ2009190

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

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

disjunctive normal formhashingmodel countingBoolean formulasfully polynomial randomized approximation scheme

Mathematics Subject Classification ID

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

Related Items (1)

Enumerating models of DNF faster: breaking the dependency on the formula size

Uses Software

• M4RI
• sharpSAT
• MayBMS

Cites Work

• Unnamed Item
• DNF sparsification and a faster deterministic counting algorithm
• Pseudorandom bits for constant depth circuits
• On deterministic approximation of DNF
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Oblivious bounds on the probability of boolean functions
• Scalable Approximation of Quantitative Information Flow in Programs
• Improved Pseudorandom Generators for Depth 2 Circuits
• Monte-Carlo approximation algorithms for enumeration problems
• The Complexity of Enumeration and Reliability Problems
• An Optimal Algorithm for Monte Carlo Estimation
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

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