An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
<|reference_start|>An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs: 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.<|reference_end|>
@article{meel2024an,
    title={An FPRAS for Model Counting for Non-Deterministic Read-Once Branching
  Programs},
    author={Kuldeep S. Meel and Alexis de Colnet},
    journal={arXiv preprint arXiv:2406.16515},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.16515},
    primaryClass={cs.DS}
}