Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases

Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:25-34, 2013.

Abstract

The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building decision-DNNF (decision decomposable negation normal form) representations of the input Boolean formulas. Decision-DNNFs are a special case of d- DNNFs where d stands for deterministic. We show that any decision-DNNF can be converted into an equivalent FBDD (free binary decision diagram) – also known as a readonce branching program (ROBP or 1-BP) – with only a quasipolynomial increase in representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-beame13a, title = {Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases}, author = {Beame, Paul and Li, Jerry and Roy, Sudeepa and Suciu, Dan}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {25--34}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/beame13a/beame13a.pdf}, url = {https://proceedings.mlr.press/r11/beame13a.html}, abstract = {The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building decision-DNNF (decision decomposable negation normal form) representations of the input Boolean formulas. Decision-DNNFs are a special case of d- DNNFs where d stands for deterministic. We show that any decision-DNNF can be converted into an equivalent FBDD (free binary decision diagram) – also known as a readonce branching program (ROBP or 1-BP) – with only a quasipolynomial increase in representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases %A Paul Beame %A Jerry Li %A Sudeepa Roy %A Dan Suciu %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-beame13a %I PMLR %P 25--34 %U https://proceedings.mlr.press/r11/beame13a.html %V R11 %X The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building decision-DNNF (decision decomposable negation normal form) representations of the input Boolean formulas. Decision-DNNFs are a special case of d- DNNFs where d stands for deterministic. We show that any decision-DNNF can be converted into an equivalent FBDD (free binary decision diagram) – also known as a readonce branching program (ROBP or 1-BP) – with only a quasipolynomial increase in representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases. %Z Reissued by PMLR on 04 October 2026.
APA
Beame, P., Li, J., Roy, S. & Suciu, D.. (2013). Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:25-34 Available from https://proceedings.mlr.press/r11/beame13a.html. Reissued by PMLR on 04 October 2026.

Related Material