• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs.
Kuldeep S. Meel ⓡ Alexis de Colnet.
In Proceedings of the International Conference on Database Theory (ICDT), March 2025.
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for representing Boolean functions. In this paper, we focus on #nFBDD, the problem of model counting for non-deterministic read-once branching programs. The #nFBDD problem is #P-hard, and it is known that there exists a quasi-polynomial randomized approximation scheme for #nFBDD. In this paper, we provide the first FPRAS for #nFBDD. Our result relies on the introduction of new analysis techniques that focus on bounding the dependence of samples.
@inproceedings{MdC25,
title={An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs},
booktitle=ICDT,
author={Meel, Kuldeep S. and de Colnet, Alexis},
abstract={
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for representing Boolean functions. In this paper, we focus on #nFBDD, the problem of model counting for non-deterministic read-once branching programs. The #nFBDD problem is #P-hard, and it is known that there exists a quasi-polynomial randomized approximation scheme for #nFBDD. In this paper, we provide the first FPRAS for #nFBDD. Our result relies on the introduction of new analysis techniques that focus on bounding the dependence of samples.
},
year={2025},
month=mar,
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://arxiv.org/abs/2406.16515},
nameorder={random},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sat Aug 09, 2025 22:48:53