---
title: "Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls"
authors:
  - "Supratik Chakraborty"
  - "Kuldeep S. Meel"
  - "Moshe Y. Vardi"
doi: ""
url: "https://ijcai.org/proceedings/2016/503"
pdf: "https://ijcai.org/proceedings/2016/0503.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3569-3575"
track: ""
keywords:
---

# Algorithmic Improvements in Approximate Counting for Probabilistic Inference: From Linear to Logarithmic SAT Calls

Supratik Chakraborty, Kuldeep S. Meel, Moshe Y. Vardi

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 3569-3575.

## 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. We use this technique to design an algorithm for #CNF with strongly probably approximately correct (SPAC) guarantees, i.e. PAC guarantee plus expected return value matching the exact model count. Our experiments show that this algorithm outperforms state-of-the-art techniques for approximate counting by 1-2 orders of magnitude in running time. We also show that our algorithm can be easily adapted to give a new fully polynomial randomized approximation scheme (FPRAS) for #DNF.