• 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 underlyingformula 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 outperformsexisting FPRAS. Our approach is based on the recent breakthrough in the context of union ofsets 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 Sun Apr 14, 2024 11:15:51