Not all FPRASs are equal: demystifying FPRASs for DNF-counting
type: Item
instance of: scholarly article
title: Not all FPRASs are equal: demystifying FPRASs for DNF-counting
zbMATH Open document ID: 1483.68498
author: Kuldeep S. Meel
author: Aditya A. Shrotri
author: Moshe Y. Vardi
published in: Constraints
publication date: 2019-11-27T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68R07
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7137186
zbMATH Keywords: model counting
zbMATH Keywords: hashing
zbMATH Keywords: disjunctive normal form
zbMATH Keywords: Boolean formulas
zbMATH Keywords: fully polynomial randomized approximation scheme
describes a project that uses: M4RI
describes a project that uses: sharpSAT
describes a project that uses: MayBMS
MaRDI profile type: Publication
full work available at URL: s10601-018-9301-x
OpenAlex ID: W2906587736
cites work: Scalable Approximation of Quantitative Information Flow in Programs
cites work: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Monte-Carlo approximation algorithms for enumeration problems
cites work: An Optimal Algorithm for Monte Carlo Estimation
cites work: Q5136333
cites work: On deterministic approximation of DNF
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: DNF sparsification and a faster deterministic counting algorithm
cites work: Pseudorandom bits for constant depth circuits
cites work: Improved Pseudorandom Generators for Depth 2 Circuits
cites work: Oblivious bounds on the probability of boolean functions
Wikidata QID: Q128681171
DOI: 10.1007/S10601-018-9301-X
description: scientific article; zbMATH DE number 7137186