• 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 scalabletechnique with strong formal guarantees, thanks to recent advances inhashing-based approximate counting. State-of-the-art hashing-basedcounting algorithms use an \NP oracle, such that the number oforacle invocations grows linearly in the number of variables n inthe input constraint. We present a new approach to hashing-basedapproximate model counting in which the number of oracle invocationsgrows logarithmically in $n$, while still providing strong theoreticalguarantees. Our experiments show that the new approach outperformsstate-of-the-art techniques for approximate counting by 1-2 ordersof 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 Sun Apr 14, 2024 11:15:51