@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{CCKM23,
  title={
    Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
  },
  author={
    Chakraborty, Diptarka and Chakraborty, Sourav and Kumar, Gunjan and Meel,
    Kuldeep S.
  },
  abstract={
    Abstract Given a Boolean formula F over n variables, the problem of model
    counting is to compute the number of solutions of F. Model counting is a
    fundamental problem in computer science with wide-ranging applications in
    domains such as quantified information leakage, probabilistic reasoning,
    network reliability, neural network verification, and more. Owing to the
    \#P-hardness of the problems, Stockmeyer initiated the study of the
    complexity of approximate counting Stockmeyer showed that $\log n$ calls to
    NP oracle are necessary and sufficient to achieve $(\varepsilon,\delta)$
    guarantees. The hashing-based framework proposed by Stockmeyer has been very
    influential in designing practical counters over the past decade, wherein
    the NP oracle calls are substituted by the SAT solver in practice. It is
    well known that NP oracle does not fully capture the behavior of SAT
    solvers, as SAT solvers are also designed to provide satisfying assignments
    when a formula is satisfiable, without additional overhead. Accordingly, the
    notion of SAT oracle has been proposed to capture the behavior of SAT solver
    wherein given a Boolean formula, a SAT oracle returns a satisfying
    assignment if the formula is satisfiable or returns unsatisfiable otherwise.
    Since the practical state of the art approximate counting techniques use SAT
    solvers, a natural question is whether a SAT oracle is more powerful than NP
    oracle in the context of approximate model counting.
    The primary contribution of this work is to study the relative power of NP
    oracle and SAT oracle in the context of approximate model counting. The
    previous techniques proposed in the context of NP oracle are weak to provide
    strong bounds in the context of SAT oracle since, in contrast to an NP
    oracle that provides only 1 bit of information, a SAT oracle can provide $n$
    bits of information. We, therefore, develop a new methodology to achieve the
    main result: a SAT oracle is no more powerful than NP oracle in the context
    of approximate model counting.
  },
  publication_type={conference},
  booktitle=ICALP,
  year={2023},
  url={../Papers/icalp23.pdf},
  month=jul,
  bib2html_rescat={Counting},
  bib2html_pubtype={Refereed Conference},
}