2026-07-23T13:07:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22971 2025-10-02T12:19:56Z ddc:004 open_access

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs Meel, Kuldeep S. de Colnet, Alexis Approximate model counting FPRAS Knowledge compilation nFBDD 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kuldeep S. Meel and Alexis de Colnet 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.30 urn:nbn:de:0030-drops-229717 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode