Scalable Algorithms for Approximate DNF Model Counting

Paul Burkhardt; David G. Harris; Kevin T. Schmitt

IJCAI 20260 citations

Scalable Algorithms for Approximate DNF Model Counting

Paul Burkhardt, David G. Harris, Kevin T. Schmitt

Abstract

Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and has asymptotically improved time and randomness complexity compared to previous methods. We also show experimentally that it out-performs prior algorithms by at least three orders of magnitude in running time and scalability.

Constraint Satisfaction and Optimization: Constraint satisfactionConstraint Satisfaction and Optimization: Solvers and toolsUncertainty in AI: Bayesian networksUncertainty in AI: InferenceUncertainty in AI: Probabilistic programming

BibTeX

@inproceedings{ijcai2026_scalablealgorith,
  title = {Scalable Algorithms for Approximate DNF Model Counting},
  author = {Paul Burkhardt and David G. Harris and Kevin T. Schmitt},
  booktitle = {IJCAI 2026},
  year = {2026}
}