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 com- puting the number of satisfying assignments, or the satisfying probability, of Boolean for- mulas can be seen, either directly or indi- rectly, as building decision-DNNF (decision decomposable negation normal form) repre- sentations 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 con- verted into an equivalent FBDD (free binary decision diagram) – also known as a read- once branching program (ROBP or 1-BP) – with only a quasipolynomial increase in rep- resentation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Lever- aging known exponential lower bounds for FBDDs, we then obtain similar exponen- tial lower bounds for decision-DNNFs which provide lower bounds for the recent algo- rithms. We also separate the power of decision-DNNFs from d-DNNFs and a gener- alization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural prob- lems 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 com- puting the number of satisfying assignments, or the satisfying probability, of Boolean for- mulas can be seen, either directly or indi- rectly, as building decision-DNNF (decision decomposable negation normal form) repre- sentations 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 con- verted into an equivalent FBDD (free binary decision diagram) – also known as a read- once branching program (ROBP or 1-BP) – with only a quasipolynomial increase in rep- resentation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Lever- aging known exponential lower bounds for FBDDs, we then obtain similar exponen- tial lower bounds for decision-DNNFs which provide lower bounds for the recent algo- rithms. We also separate the power of decision-DNNFs from d-DNNFs and a gener- alization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural prob- lems 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 com- puting the number of satisfying assignments, or the satisfying probability, of Boolean for- mulas can be seen, either directly or indi- rectly, as building decision-DNNF (decision decomposable negation normal form) repre- sentations 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 con- verted into an equivalent FBDD (free binary decision diagram) – also known as a read- once branching program (ROBP or 1-BP) – with only a quasipolynomial increase in rep- resentation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Lever- aging known exponential lower bounds for FBDDs, we then obtain similar exponen- tial lower bounds for decision-DNNFs which provide lower bounds for the recent algo- rithms. We also separate the power of decision-DNNFs from d-DNNFs and a gener- alization of decision-DNNFs known as AND- FBDDs. Finally we show how these imply exponential lower bounds for natural prob- lems 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