@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@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},
}