• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Engineering an Efficient Approximate DNF-Counter.
Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel and Maciej Obremski.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), August 2023.
Model counting is a fundamental problem with many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In this work, we focus on a variant of this problem where the underlying formula is expressed in Disjunctive Normal Form (DNF), also known as #DNF. This problem has been shown to be #P-complete, making it intractable to solve exactly. Much research has therefore been focused on obtaining approximate solutions, particularly in the form of $(\epsilon, \delta)$ approximations. The primary contribution of this paper is a new approach, called dnfstream, to approximate #DNF counting that achieves (nearly) optimal time complexity and outperforms existing FPRAS. Our approach is based on the recent breakthrough in the context of union of sets in streaming. We demonstrate the effectiveness of our approach through extensive experiments and show that it provides an affirmative answer to the challenge of efficiently computing #DNF.
@inproceedings{SACMO23,
title={Engineering an Efficient Approximate DNF-Counter},
author={
Soos, Mate and
Aggarwal, Divesh and
Chakraborty, Sourav and
Meel, Kuldeep S. and
Obremski, Maciej
},
abstract={
Model counting is a fundamental problem with many practical applications,
including query evaluation in probabilistic databases and
failure-probability estimation of networks. In this work, we focus on a
variant of this problem where the underlying
formula is expressed in Disjunctive Normal Form (DNF), also known as \#DNF.
This problem has been shown to be \#P-complete, making it intractable to
solve exactly. Much research has therefore been focused on obtaining
approximate solutions, particularly in the form of $(\epsilon, \delta)$
approximations.
The primary contribution of this paper is a new approach, called dnfstream,
to approximate \#DNF counting that achieves (nearly) optimal time complexity
and outperforms
existing FPRAS. Our approach is based on the recent breakthrough in the
context of union of
sets in streaming. We demonstrate the effectiveness of our approach through
extensive experiments and show that it provides an affirmative answer to the
challenge of efficiently computing \#DNF.
},
publication_type={conference},
booktitle=IJCAI,
year={2023},
month=aug,
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={../Papers/ijcai23-sacmo.pdf},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21