• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls .
Supratik Chakraborty, Kuldeep S. Meel and Moshe Y. Vardi.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), July 2016.
Probabilistic inference via model counting has emerged as a scalable technique with strong formal guarantees, thanks to recent advances in hashing-based approximate counting. State-of-the-art hashing-based counting algorithms use an \NP oracle, such that the number of oracle invocations grows linearly in the number of variables n in the input constraint. We present a new approach to hashing-based approximate model counting in which the number of oracle invocations grows logarithmically in $n$, while still providing strong theoretical guarantees. Our experiments show that the new approach outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time.
@inproceedings{CMV16,
title={
Algorithmic Improvements in Approximate Counting for Probabilistic
Inference:
From Linear to Logarithmic SAT Calls
},
author={Chakraborty, Supratik and Meel, Kuldeep S. and Vardi, Moshe Y.},
code={https://bitbucket.org/kuldeepmeel/approxmc},
year={2016},
bib2html_dl_pdf={../Papers/ijcai16_counting.pdf},
month=jul,
booktitle=IJCAI,
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
abstract={
Probabilistic inference via model counting has emerged as a scalable
technique with strong formal guarantees, thanks to recent advances in
hashing-based approximate counting. State-of-the-art hashing-based
counting algorithms use an {\NP} oracle, such that the number of
oracle invocations grows linearly in the number of variables n in
the input constraint. We present a new approach to hashing-based
approximate model counting in which the number of oracle invocations
grows logarithmically in $n$, while still providing strong theoretical
guarantees. Our experiments show that the new approach outperforms
state-of-the-art techniques for approximate counting by 1-2 orders
of magnitude in running time.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21