An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs

Meel, Kuldeep S.; de Colnet, Alexis

doi:10.4230/LIPIcs.ICDT.2025.30

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs

Kuldeep S. Meel ⓡ

University of Toronto, Canada Alexis de Colnet ⓡ

TU Wien, Austria

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.

Keywords and phrases:

Approximate model counting, FPRAS, Knowledge compilation, nFBDD

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

Related Version:

Full Version: https://arxiv.org/abs/2406.16515

Acknowledgements:

This research was initiated at Dagstuhl Seminar 24171 on “Automated Synthesis: Functional, Reactive and Beyond” (https://www.dagstuhl.de/24171). We gratefully acknowledge the Schloss Dagstuhl – Leibniz Center for Informatics for providing an excellent environment and support for scientific collaboration.

Funding:

Meel acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), funding reference number RGPIN-2024-05956; de Colnet is supported by the Austrian Science Fund (FWF), ESPRIT project FWF ESP 235. This work was done in part while de Colnet was visiting the University of Toronto.¹¹1 The authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by ⓡ. The publicly verifiable record of the randomization is available at https://www.aeaweb.org/journals/policies/random-author-order/search

DOI:

10.4230/LIPIcs.ICDT.2025.30

Event:

28th International Conference on Database Theory (ICDT 2025)

Editors:

Sudeepa Roy and Ahmet Kara

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Read-once branching programs or binary decision diagrams are fundamental data structures in computer science used to represent Boolean functions. Their variants have been discovered multiple times across various sub-fields of computer science, and consequently, they are referred to by many acronyms [15, 9, 23]. In this paper, we focus on non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD).

We study the following computational problem:

#nFBDD.

Given a non-deterministic read-once branching program $B$ over a Boolean set of variables $X$ , compute the number of models of $B$ , i.e., the number of assignments over $X$ that $B$ maps to $1$ .

From a database perspective, #nFBDD is an important problem owing to the recent connections between query evaluation and knowledge compilation [13, 14, 21, 20, 2, 1]. The field of knowledge compilation has its origins in the artificial intelligence community, where functions represented in input languages are compiled into target languages that can support queries tractably (often viewed as polynomial time) [10]. The typical queries of interest are satisfiability, entailment, enumeration, and counting.

The target languages in the context of databases have been variants of binary decision diagrams, also referred to as branching programs, and circuits in decomposable negation normal form (DNNF) [2, 1]. A binary decision diagram is a representation of a Boolean function as a directed acyclic graph where the nodes correspond to variables and the sinks correspond to values, i.e., $0$ or $1$ . One of the most well-studied forms is the ordered binary decision diagram (OBDD), where the nodes correspond to variables and, along every path from root to leaf, the variables appear in the same order [9]. A generalization of OBDD is nOBDD, where internal nodes can also represent disjunction ( $\vee$ ) gates.

nFBDD are a natural generalization of nOBDDs, as they do not impose restrictions on the ordering of Boolean variables. Since nFBDD do not impose such restrictions, they are known to be exponentially more succinct than nOBDD; that is, there exist functions for which the smallest nOBDD is exponentially larger than the smallest nFBDD [4]. From this viewpoint, nFBDDs occupy a space between nOBDD and DNNF circuits, as they are exponentially more succinct than nOBDDs, while DNNFs are quasi-polynomially more succinct than nFBDD [8, 4].

In the context of databases, the connection between knowledge compilation and query evaluation has been fruitful, leading to the discovery of both tractable algorithms and lower bounds. Of particular note is the application of the knowledge compilation paradigm in query evaluation on probabilistic databases [14], Shapley value computation [11], the enumeration of query answers, probabilistic graph homomorphism [5], counting answers to queries [7]. The knowledge compilation-based approach involves first representing the database task as a query over a Boolean function and then demonstrating that the corresponding Boolean function has a tractable representation in a given target language, which also supports the corresponding query in polynomial time [3]. For example, in the context of query evaluation over probabilistic databases, one can show that the problem of probabilistic query evaluation can be represented as a weighted model counting problem over nOBDD when the underlying query is a path query [5]. Since there is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem of model counting over nOBDD [6], it follows that probabilistic query evaluation for regular path queries over tuple-independent databases admits an FPRAS [5]. In the context of aggregation tasks, the underlying query is often model counting and its variants [19].

The aforementioned strategy makes it desirable to have target languages that are as expressive as possible while still supporting queries such as counting in polynomial time. In this context, the recent flurry of results has been enabled by the breakthrough of Arenas, Croquevielle, Jayaram, and Riveros, who showed that the problem of #nOBDD admits an FPRAS [6]. As mentioned earlier, nOBDD imposes a severe restriction on variable ordering, i.e., along every path from root to leaf, the variable ordering remains the same. nFBDD generalizes nOBDD by alleviating this restriction, thereby enabling succinct representations for several functions that require exponentially large nOBDD. Since nFBDD generalize nOBDD, the #P-hardness of #nFBDD, the problem of model counting over nFBDD, immediately follows. Accordingly, in light of the recent discovery of FPRAS for #nOBDD, an important open question is whether there exists an FPRAS for #nFBDD. The best known prior result provides a quasi-polynomial time algorithm owing to reduction of nFBDD to DNNF (and accordingly $(+,\times)$ -programs) [12]. As noted in Section 2.1, the techniques developed in the context of design of FPRAS for #nOBDD do not extend to handle the case for #nFBDD and therefore, design of FPRAS for #nFBDD would require development of new techniques.

The primary contribution of our work is to answer the aforementioned question affirmatively, which is formalized in the following theorem.

Theorem 1.

Let $B$ be an nFBDD over $n$ variables, $\varepsilon>0$ and $\delta>0$ . Algorithm $\textup{{approxMCnFBDD}}(B,\varepsilon,\delta)$ runs in time $O(n^{5}\varepsilon^{-4}\log(\delta^{-1})|B|^{6}\log|B|)$ and returns $\mathsf{est}$ with the guarantee that $\Pr\left[\mathsf{est}\in(1\pm\varepsilon)|B^{-1}(1)|\right]\geq 1-\delta.$

Organization of the paper.

We start with background on nFBDD in Section 2. The different components of the FPRAS are described in Section 4 and the analysis is split in three parts: in Section 5 we introduce the key concept of derivation paths, in Section 6 we describe the particular framework for the analysis, and in Section 7 we go through the proof of the FPRAS guarantees. For space reason, the proofs of several intermediate results are deferred to the appendix.

2 Background

Given a positive integer $n$ and $m$ an integer less than $n$ , $[n]$ denotes the set $\{1,2,\dots,n\}$ and $[m,n]$ the set $\{m,m+1,\dots,n\}$ . For $a$ , $b$ and $\varepsilon$ three real numbers with $\varepsilon>0$ , we use $a\in(1\pm\varepsilon)b$ to denote $(1-\varepsilon)b\leq a\leq(1+\varepsilon)b$ , similarly, $a\in\frac{b}{1\pm\varepsilon}$ stands for $\frac{b}{1+\varepsilon}\leq a\leq\frac{b}{1-\varepsilon}$ . We sometimes uses the special value $\infty$ and in particular that $\frac{1}{\infty}$ equals $0$ .

Boolean variables take value $0$ (false) or $1$ (true). An assignment $\alpha$ to a set $X$ of Boolean variables is mapping from $X$ to $\{0,1\}$ . We sometimes see $\alpha$ as a set $\{x\mapsto\alpha(x)\mid x\in X\}$ . We denote by $\alpha_{\emptyset}$ the empty assignment, which corresponds to the empty set. The set of assignments to $X$ is denoted $\{0,1\}^{X}$ . A Boolean function $f$ over $X$ is a mapping $\{0,1\}^{X}$ to $\{0,1\}$ . The models of $f$ are the assignments mapped to $1$ by $f$ . When not explicit, the set of variables assigned by $\alpha$ is denoted by $var(\alpha)$ . When $var(\alpha^{\prime})\cap var(\alpha)=\emptyset$ , we denote by $\alpha\cup\alpha^{\prime}$ the assignment to $var(\alpha^{\prime})\cup var(\alpha)$ consistent with both $\alpha$ and $\alpha^{\prime}$ . For $S$ and $S^{\prime}$ two sets of assignments, we write $S\otimes S^{\prime}=\{\alpha\cup\alpha^{\prime}\mid\alpha\in S,\,\alpha^{% \prime}\in S^{\prime}\}$ .

nBDD.

A binary decision diagram (BDD) is a directed acyclic graph (DAG) with a single source node $q_{\text{source}}$ , two sinks labeled $0$ and $1$ , and where each internal node is labeled by a Boolean variable $x$ and has two outgoing edges: the $0$ -edge going to the $0$ -child $q_{0}$ and and the $1$ -edge going to the $1$ -child $q_{1}$ (potentially $q_{0}=q_{1}$ ). Internal nodes are called decision nodes and are written $ite(x,q_{1},q_{0})$ (if $x=1$ then go to $q_{1}$ else go to $q_{0}$ ). A path in the DAG contains a variable $x$ if it contains a node $ite(x,q_{1},q_{0})$ . Every variables assignment $\alpha$ corresponds to the unique path that starts from the source and, on a decision node $ite(x,q_{1},q_{0})$ follows the $\alpha(x)$ -edge. Non-deterministic BDD (nBDD) also admit guess nodes: unlabeled nodes with arbitrarily many children. When a path for an assignment reaches a guess node it can pursue to any child, so several paths can correspond to the same assignment in an nBDD. For $q$ a node in an nBDD $B$ , $var(q)$ denotes the set of variables labeling decision nodes reachable from $q$ (including $q$ ) in the usual sense of graph reachibility. We note $var(B)=var(q_{\text{source}})$ . $B$ computes a Boolean function over $var(B)$ whose models are the assignments for which at least one path reaches the $1$ -sink. Every node $q$ of $B$ is itself the source of an nBDD and therefore represents a function over $var(q)$ whose set of models we note $\mathsf{mod}(q)$ . So $B^{-1}(1)=\mathsf{mod}(q_{\text{source}})$ . The function computed by an nBDD is also that computed by the circuit obtained replacing every decision node $ite(x,q_{1},q_{0})$ by $(\neg x\land q_{0})\lor(x\land q_{1})$ and every guess node with children $q_{1},\dots,q_{k}$ by $q_{1}\lor\dots\lor q_{k}$ . Thus, we call $\lor$ -nodes the guess nodes in this paper. The size of an nBDD $B$ , denoted by $|B|$ , is its number of edges.

nFBDD.

An nBDD is free (nFBDD) when every path contains every variable at most once. There are also called in the literature read-once non-deterministic branching programs (1-NBP). Note that in an nFBDD, variables may appear in different order depending on the path. When the order of occurrence of the variables is consistent among all paths of the nFBDD we say that we have an ordered nBDD (nOBDD). We call an nFBDD $1$ -complete when along every path from the source to the $1$ -sink, every variable occurs exactly once. We call an nFBDD $0$ -reduced when it contains no decision nodes $ite(x,0\text{-sink},0\text{-sink})$ and no $\lor$ -nodes that have the $0$ -sink among their children. Technically, $0$ -reduced nFBDD cannot represent functions with no models, but these functions are not considered in this paper. An nFBDD is alternating when its source node is a $\lor$ -node, when every $\lor$ -node only has decision nodes for children, and when every decision node has only $\lor$ -nodes and sinks for children.

Lemma 2.

Every nFBDD $B$ over $n$ variables can be made $1$ -complete, $0$ -reduced, and alternating in time $O(n|B|^{2})$ .

Proof sketch.

First, we make $B$ $0$ -reduced by repeating the following until reaching a fixed point: replace all nodes $ite(x,0\text{-sink},0\text{-sink})$ by the $0$ -sink, remove the $0$ -sink from $\lor$ -nodes’ children, and replace all $\lor$ -nodes with no child by the $0$ -sink. Doing these replacements bottom-up in $B$ takes time $O(|B|)$ and results in a $0$ -reduced nFBDD $B^{\prime}$ with $|B^{\prime}|\leq|B|$ .

Second, we make $B^{\prime}$ alternating w.r.t. the $\lor$ -nodes. Replace every $\lor$ -node that have the $1$ -sink as a child by the $1$ -sink. At that point, no sink is a child of any $\lor$ -node. Next, for every $\lor$ -node $q$ in $B^{\prime}$ , if $q$ has a parent $q^{\prime}$ that is a $\lor$ -node, then remove $q$ from $q$ ’s children and add all of $q$ ’s children to $q^{\prime}$ ’s children. Doing this replacement bottom-up yields an nFBDD whose $\lor$ -nodes all have only decision nodes children. The number of children of each $\lor$ -node is increased by at most $|B^{\prime}|$ so the running time is $O(|B^{\prime}|^{2})=O(|B|^{2})$ . Let $B^{\prime\prime}$ be the resulting nFBDD. $B^{\prime\prime}$ is still $0$ -reduced.

Third, we make $B^{\prime}$ $1$ -complete. For every $q\in B^{\prime\prime}$ , let $\mathsf{children}(q)=(q_{1},\dots,q_{k})$ . While there exists $i\in[k]$ such that $var(q_{i})\neq var(q)$ , choose $x\in var(q)\setminus var(q_{i})$ and replace $q_{i}$ by the node $ite(x,q_{i},q_{i})$ in the children of $q$ . This adds at most $n$ decision nodes per original child of $q$ . So doing this for all decision nodes takes time $O(n|B^{\prime\prime}|)=O(n|B|^{2})$ and gives a $1$ -complete nFBDD $B^{\prime\prime\prime}$ which is still $0$ -reduced and alternating w.r.t. the $\lor$ nodes.

Finally, to make $B^{\prime\prime\prime}$ alternating, we just have to consider every $ite(x,q_{1},q_{0})$ and, if $q_{b}$ is not a $\lor$ -node or a sink, to replace it by a $\lor$ -node whose unique child is $q_{b}$ . This takes time $O(B^{\prime\prime\prime})$ . One $\lor$ -node is added for the source of the nFBDD if needed. $\hfill\blacktriangleleft$

The nodes of $1$ -complete $0$ -reduced alternating nFBDD are organized in layers $L_{0},L_{1},\dots,$ $L_{2n}$ . $L_{0}$ contains the sinks and, for $1\leq i\leq 2n$ the layer $L_{i}$ contains all nodes whose children (except the $0$ -sink) are in $L_{i-1}$ . We write $L_{\leq i}=L_{0}\cup\dots\cup L_{i}$ , and similarly for $L_{\geq i}$ , $L_{<i}$ and $L_{>i}$ . Note that for all $1\leq i\leq n$ , $L_{2i-1}$ contains only decision nodes whereas $L_{2i}$ contains only $\lor$ -nodes. Importantly, we assume an arbitrary ordering on the children of the nodes; for every node $q$ we have a sequence (not a set) $\mathsf{children}(q)$ of its children.

FPRAS.

For a counting problem that, given an input $x$ of size $|x|$ , aims at computing some integer value $N(x)$ , a fully polynomial-time randomized approximation scheme (FPRAS) is an algorithm that, given $x$ , $\varepsilon>0$ , and $0<\delta<1$ , runs in time polynomial in $|x|$ , $1/\varepsilon$ , and $\log(1/\delta)$ , and returns $\tilde{N}$ with the guarantee that $\Pr\left[\tilde{N}\in(1\pm\varepsilon)N(x)\right]\geq 1-\delta.$ In this paper we give an #FPRAS for the problem #nFBDD.
#nFBDD Input: an nFBDD $B$ Output: its number of models $|B^{-1}(1)|$

2.1 Related Work

As noted in Section 1, the literature on binary decision diagrams is extensive; therefore, we will focus solely on related results in the context of the model counting problem. The problem of #nFBDD is #P-complete: membership in #P is immediate as every assignment can be evaluated in PTIME, and the #P-hardness follows from the observation that the problem of #DNF, i.e., counting the number of satisfying assignments of Boolean formulas in Disjunctive Normal Form, is #P-hard [22]. Moreover, every DNF can be represented as an nFBDD such that the size of the resulting nFBDD is polynomial in the size of the DNF. Furthermore, it is also known that the problem of #nOBDD is SpanL-complete [6].

Given the #P-hardness, a natural direction of research is to understand the complexity of approximation. The discovery of polynomial-time randomized approximation schemes for #P-hard problems has been of long-standing interest and has led to several theoretically deep and elegant results. One such result was that of Karp and Luby [17] in the context of #DNF, relying on Monte Carlo sampling. Building on Monte Carlo sampling, Kannan, Sampath, and Mahaney [16] proposed a quasi-polynomial running time approximation scheme for #nOBDD.²²2The result of [16] was stated for regular languages, but the underlying techniques can handle #nOBDD. In a follow-up work [12], this result was extended to handle context-free grammars by reducing the problem of counting words of a context-free grammar to estimating the support size of multilinear $(+,\times)$ -programs. It is straightforward to see that the same reduction can be applied in the context of #DNNF, implying a quasi-polynomial runtime approximation for #nFBDD. Since then, the question of the existence of a fully polynomial-time randomized approximation scheme for #nFBDD and its generalizations has remained open.

In a major breakthrough, Arenas et al. [6] provided an FPRAS for #nOBDD. Their technique relied on union of sets estimation à la Karp-Luby and the generation of independent samples via the self-reducibility union property.³³3The term self-reducibility union property was coined by Meel, Chakraborty, and Mathur [18] to explain the high-level idea of [6]. The self-reducibility union property can be informally stated as follows: The set of models conditioned on a given partial assignment (according to the variable ordering of the given nOBDD) can be expressed as the union of models of the states of the given nOBDD. In a follow-up work [7], Arenas et al. observed that the problem of model counting over structured DNNF (st-DNNF) circuits also admits FPRAS. In this context, it is worth highlighting that the self-reducibility union property does not hold for nFBDD and there exists exponential separation between nFBDD and st-DNNF, i.e., there is a family of functions for which the smallest FBDD are exponentially smaller than the smallest st-DNNF, and therefore, the problem of whether there exists an FPRAS for #nFBDD remains open.

3 Technical Overview

Our algorithm proceeds in a bottom-up manner and for every node $q$ of given nFBDD $B$ , we keep: (1) a number $p(q)\in(0,1]$ which seeks to approximate $\frac{1}{|\mathsf{mod}(q)|}$ , and therefore, $\frac{1}{p(q)}$ can be used to estimate $|\mathsf{mod}(q)|$ , and (2) $n_{s}n_{t}$ sets of samples $S^{1}(q),\dots,S^{n_{s}n_{t}}(q)$ , each a subset of $\mathsf{mod}(q)$ , where $n_{s}$ and $n_{t}$ are polynomial in $n=|var(B)|$ , $\varepsilon^{-1}$ and $\log|B|$ . Few comments are in order: we keep many ( $n_{s}\cdot n_{t}$ ) independent sets of samples so as to rely on the median of means estimator. As mentioned earlier, our algorithm works in bottom-up manner, in particular, for a node $q$ , we will compute $(p(q),\{S^{r}(q)\}_{r})$ using the values of $p(\cdot)$ and $\{S^{r}(\cdot)\}_{r}$ of its children.

Ideally, we want every model of $q$ to be in $S^{r}(q)$ identically and independently with probability $p(q)$ , and thus tat the expected size of $S^{r}(q)$ is small. However, obtaining iid samples is computationally expensive, which resulted in quasi-polynomial runtimes in earlier studies [12]. Recent works on FPRAS for nOBDD achieved independence by leveraging self-reducibility union property [6, 7], but, as remarked in Section 2.1, the self-reducibility union property does not hold for nFBDD and therefore, it is not known how to accomplish independence among samples without giving up on the desiderata of polynomial time.

The key insight in our approach is to give up the desire for independence altogether, in particular, we do not even ensure pairwise independence, i.e., even for $\alpha,\alpha^{\prime}\in\mathsf{mod}(q)$ , it may not be the case that $\Pr[\alpha\in S^{r}(q)|\alpha^{\prime}\in S^{r}(q)]=\Pr[\alpha\in S^{r}(q)]$ . Of course, we do need to quantify the dependence. In order to discuss the dependence, we first discuss how we update $p(q)$ and $S^{r}(q)$ for decision nodes and $\lor$ -nodes.

$\blacksquare$

Let $q=ite(x,q_{1},q_{0})$ . Then we compute $p(q)$ and $S^{r}(q)$ as $p(q)=\left(\frac{1}{p(q_{0})}+\frac{1}{p(q_{1})}\right)^{-1}$ and $S^{r}(q)=\left(\textup{{reduce}}\left(S^{r}(q_{0}),\frac{p(q)}{p(q_{0})}\right% )\otimes\{x\mapsto 0\}\right)\cup\left(\textup{{reduce}}\left(S^{r}(q_{1}),% \frac{p(q)}{p(q_{1})}\right)\otimes\{x\mapsto 1\}\right)$ , where $\textup{{reduce}}(S,p)$ is the operation that keeps each element of a set $S$ with probability $p$ .
$\blacksquare$

Let $q$ be a $\lor$ -node such that $q=q_{1}\lor q_{2}$ (assuming two children for simplicity). Furthermore, for simplicity of exposition and for the sake of high-level intuition, assume $p(q_{1})=p(q_{2})$ . The technical difficulty for $\lor$ -nodes arises from the fact that it is possible that for a given $\alpha\in\mathsf{mod}(q)$ , we have $\alpha\in\mathsf{mod}(q_{1})\cap\mathsf{mod}(q_{2})$ . Therefore, in order to ensure no $\alpha$ has undue advantage even if it lies in the models set of multiple children, we update $p(q)$ and $S^{r}(q)$ as follows: we first compute $\rho=\min(p(q_{1}),p(q_{2}))$ and $\hat{S}^{r}(q)=S^{r}(q_{1})\cup(S^{r}(q_{2})\setminus\mathsf{mod}(q_{1}))$ and then $p(q)=\underset{0\leq j<n_{t}}{\mathsf{median}}\left(\frac{1}{\rho\cdot n_{s}}% \sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}|\hat{S}^{r}(q)|\right)^{-1}$ followed by $S^{r}(q)=\textup{{reduce}}\left(\hat{S}^{r}(q),\frac{p(q)}{\rho}\right)$ .

Observe that the usage of $S^{r}(q_{2})\setminus\mathsf{mod}(q_{1})$ ensures that for every $\alpha\in\mathsf{mod}(q)$ , there is exactly one child of $q^{\prime}\in\mathsf{children}(q)$ such that if $\alpha\in\hat{S}^{r}(q)$ then $\alpha\in S^{r}(q^{\prime})$ , and therefore, no $\alpha$ has undue advantage.

It is worth re-emphasizing the crucial departure in our work from earlier efforts is embrace of dependence. For instance, consider $q=q_{1}\lor q_{2}$ and $\hat{q}=q_{1}\lor q_{3}$ , then $S^{r}(q)$ and $S^{r}(\hat{q})$ will of course be reusing samples $S^{r}(q_{1})$ , and therefore, do not even have pairwise independence. Now, of course, we need to bound dependence so as to retain any hope of computing $p(q)$ from $S^{r}(q)$ . To this end, we focus on the following quantity of interest: $\Pr[\alpha\in S^{r}(q)\mid\alpha^{\prime}\in S^{r}(q)]$ for $\alpha,\alpha^{\prime}\in\mathsf{mod}(q)$ , which determines the variance for the estimator. In this regard, for every $(\alpha,q)$ , we can define a derivation path, denoted as $\mathsf{path}(\alpha,q)$ , where for every $\lor$ -node, $\mathsf{path}(\alpha,q)$ is $\mathsf{path}(\alpha,q^{\prime})$ appended with $q$ , where $q^{\prime}$ is the first child of q such that $\alpha\in\mathsf{mod}(q^{\prime})$ . The key observation is that our computations ensure $\Pr[\alpha\in S^{r}(q)\mid\alpha^{\prime}\in S^{r}(q)]$ depends on the first node (starting from the $1$ -sink) $q^{*}$ where the derivation paths $\mathsf{path}(\alpha,q)$ and $\mathsf{path}(\alpha,q^{\prime})$ diverge. In particular, it turns out:

\Pr[\alpha\in S^{r}(q)|\alpha^{\prime}\in S^{r}(q)]\leq\frac{p(q)}{p(q^{*})}.

One might wonder whether the above expression suffices: it turns out it does, because the number of pairs $(\alpha,\alpha^{\prime})$ whose derivation paths diverge for the first time at $q^{*}$ can be shown to be bounded by $\frac{|\mathsf{mod}(q)|^{2}}{|\mathsf{mod}(q^{*})|}$ , which suffices to show that the variance of the estimator can be bounded by constant factor of square of its mean, thus allowing us to use median of means estimator.

We close off by remarking that the situation is more nuanced than previously described, as $p(q)$ is itself a random variable. Although the high-level intuition remains consistent, the technical analysis requires coupling, based on a carefully defined random process, detailed in Section 6. Simplifying the rigorous technical argument would be an interesting direction of future research.

4 Algorithm

The core of our FPRAS, approxMCnFBDD_core, takes in a $1$ -complete, $0$ -reduced and alternating nFBDD $B$ . $B$ ’s nodes are processed in bottom-up order, so from the sinks to the source. For each node $q$ , the algorithm computes $p(q)$ which seeks to estimate $|\mathsf{mod}(q)|^{-1}$ , and polynomially-many subsets of $\mathsf{mod}(q)$ called sample sets: $S^{1}(q),\dots,S^{N}(q)$ . The algorithm stops after processing the source node $q_{\text{source}}$ and returns $p(q_{\text{source}})^{-1}$ . The procedure that computes the content of $S^{r}(q)$ and the value for $p(q)$ is $\textup{{estimateAndSample}}(q)$ . Since this procedure uses randomness, the $\{S^{r}(q)\}_{r}$ and $p(q)$ are random variables. Our FPRAS works towards ensuring that “ $\Pr[\alpha\in S^{r}(q)]=p(q)$ ” holds true for every $q\in B$ and $\alpha\in\mathsf{mod}(q)$ . Thus, if $p(q)$ is a good estimate of $|\mathsf{mod}(q)|^{-1}$ , then $S^{r}(q)$ should be small in expectation. We put the equality between quotes because it does not make much sense as the left-hand side is a probability, so a fixed number, whereas the right-hand side is a random variable.

Algorithm 1

\textup{{estimateAndSample}}(q)

with

q=ite(x,q_{1},q_{0})

.

1

p(q)=(\frac{1}{p(q_{0})}+\frac{1}{p(q_{1})})^{-1}

2 for $1\leq r\leq n_{s}n_{t}$ do

3

S^{r}(q)=\left(\textup{{reduce}}\left(S^{r}(q_{0}),\frac{p(q)}{p(q_{0})}\right% )\otimes\{x\mapsto 0\}\right)\cup\left(\textup{{reduce}}\left(S^{r}(q_{1}),% \frac{p(q)}{p(q_{1})}\right)\otimes\{x\mapsto 1\}\right)

4

Decision nodes and $\lor$ -nodes are handled differently by estimateAndSample. When $q$ is a decision node $ite(x,q_{1},q_{0})$ , $p(q)$ is computed deterministically from $p(q_{0})$ and $p(q_{1})$ , and $S^{r}(q)$ is reduced from $(S^{r}(q_{0})\otimes\{x\mapsto 0\})\cup(S^{r}(q_{1})\otimes\{x\mapsto 1\})$ using the reduce procedure.

Algorithm 2

\textup{{reduce}}(S,p)

with

p\in[0,1]

.

1

S^{\prime}\leftarrow\emptyset

2 for $s\in S$ do

3 add

s

to

S^{\prime}

with probability

p

4

return $S^{\prime}$

$\textup{{estimateAndSample}}(q)$ is more complicated when $q$ is a $\lor$ -node. We explain it gradually. For starter, let $q=q_{1}\lor\dots\lor q_{k}$ with its children ordered as follows: $(q_{1},\dots,q_{k})$ , and consider the problem of approximating $|\mathsf{mod}(q)|$ when a sample set $S(q_{i})\subseteq\mathsf{mod}(q_{i})$ is available for every $i\in[k]$ and $b\in\{0,1\}$ with the guarantee that $\Pr[\alpha\in S(q_{i})]=\rho$ holds for every $\alpha\in\mathsf{mod}(q_{i})$ . Every $S(q_{i})$ is a subset of $\mathsf{mod}(q)$ . We compute $\hat{S}(q)=\textup{{union}}(q,S(q_{1}),\dots,S(q_{k}))$ as follows: for every $\alpha\in S(q_{i})$ , $\alpha$ is added to $\hat{S}(q)$ if and only if $q_{i}$ is the first child of $q$ for which $\alpha$ is a model. Simple computations show that $\Pr[\alpha\in\hat{S}(q)]=\rho$ holds for every $\alpha\in\mathsf{mod}(q)$ , and therefore $\rho^{-1}|\hat{S}(q)|$ is an unbiased estimate of $|\mathsf{mod}(q)|$ (i.e., the expected value of the estimate is $|\mathsf{mod}(q)|$ ).

Algorithm 3

\textup{{union}}(q,S_{1},\dots,S_{k})

with

\mathsf{children}(q)=(q_{1},\dots,q_{k})

.

1

S^{\prime}=\emptyset

2 for $1\leq i\leq k$ do

3 for $\alpha\in S_{i}$ do

4 if

\alpha\not\in\mathsf{mod}(q_{j})

for every

j<i

then add

\alpha

to

S^{\prime}

5

6

return $S^{\prime}$

Now suppose that for every $i$ , we only know that $\Pr[\alpha\in S(q_{i})]=p(q_{i})$ for every $\alpha\in\mathsf{mod}(q_{i})$ for some number $p(q_{i})$ independent of $\alpha$ . Then we normalize the probabilities before computing the union. This is done using the reduce procedure. Let $\rho=\min(p(q_{1}),\dots,p(q_{k}))$ and $\bar{S}(q_{i})=\textup{{reduce}}(S(q_{i}),\frac{\rho}{p(q_{i})})$ . We have that $\Pr[\alpha\in\bar{S}(q_{i})]=\rho$ holds for every $\alpha\in\mathsf{mod}(q)$ . So $\hat{S}(q)=\textup{{union}}(q,\bar{S}(q_{1}),\dots,\bar{S}(q_{k}))$ , and $\rho^{-1}|\hat{S}(q)|$ is an unbiased estimate of $|\mathsf{mod}(q)|$ .

Algorithm 4

\textup{{estimateAndSample}}(q)

with

q=q_{1}\lor\dots q_{k}

and

\mathsf{children}(q)=(q_{1},\dots,q_{k})

.

1

\rho=\min(p(q_{1}),\dots,p(q_{k}))

2 for $1\leq r\leq n_{s}n_{t}$ do

3

\hat{S}^{r}(q)=\textup{{union}}\left(q,\textup{{reduce}}\big{(}S^{r}(q_{1}),% \frac{\rho}{p(q_{1})}\big{)},\dots,\textup{{reduce}}\big{(}S^{r}(q_{k}),\frac{% \rho}{p(q_{k})}\big{)}\right)

4

5for $0\leq j<n_{t}$ do

6

M_{j}=\frac{1}{\rho\cdot n_{s}}\sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}|\hat{S}^{r% }(q)|

7

8

\hat{\rho}=\underset{0\leq j<n_{t}}{\mathsf{median}}(M_{j})^{-1}

9

p(q)=\min(\rho,\hat{\rho})

10 for $1\leq r\leq n_{s}n_{t}$ do

11

S^{r}(q)=\textup{{reduce}}\big{(}\hat{S}^{r}(q),\frac{p(q)}{\rho}\big{)}

12

To find an estimate that is concentrated around $|\mathsf{mod}(q)|$ , we use the “median of means” technique. Suppose that instead of one sample set $S(q_{i})$ we have several sample sets $S^{1}(q_{i}),S^{2}(q_{i}),\dots,S^{N}(q_{i})$ all verifying $\Pr[\alpha\in S^{r}(q_{i})]=p(q_{i})$ . Then define $\bar{S}^{r}(q_{i})$ similarly to $\bar{S}(q_{i})$ and $\hat{S}^{r}(q)$ similarly to $\hat{S}(q)$ . Each $\rho^{-1}|\hat{S}^{r}(q)|$ is an estimate of $|\mathsf{mod}(q)|$ . Say $N=n_{s}n_{t}$ and partition $\hat{S}^{1}(q),\hat{S}^{2}(q),\dots,\hat{S}^{N}(q)$ into $n_{t}$ batches of $n_{s}$ sets. The median of means technique computes the average size $M_{j}=\frac{1}{n_{s}}\sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}|\hat{S}^{r}(q)|$ over each batch and uses $\rho^{-1}\mathsf{median}(M_{1},\dots,M_{n_{t}})$ to estimate $|\mathsf{mod}(q)|$ . The mean computation aims at reducing the variance of the estimate. The parameter $n_{s}$ can be chosen so that $\Pr[\rho^{-1}M_{j}\in(1\pm\varepsilon)|\mathsf{mod}(q)|]>\frac{1}{2}$ holds true. With the appropriate value for $n_{t}$ , $\rho^{-1}\mathsf{median}(M_{1},\dots,M_{n_{t}})$ lies in $(1\pm\varepsilon)|\mathsf{mod}(q)|$ with high probability (though the estimate is not unbiased anymore).

So this is how estimateAndSample works for $\lor$ -nodes. The median of means serves to compute $\hat{\rho}$ , the inverse of the estimate of $|\mathsf{mod}(q)|$ which in turn is used to compute $p(q)$ . When $q$ is not the source node $q_{\text{source}}$ , we compute sample sets $S^{r}(q)$ in preparation for processing of $q$ ’s ancestors. For this we reuse $\hat{S}^{r}(q)$ and compute $S^{r}(q)=\textup{{reduce}}(\hat{S}^{r}(q),\frac{p(q)}{\rho})$ .

Algorithm 5

\textup{{approxMCnFBDD\_core}}(B,n,n_{s},n_{t},\theta)

.

1

p(1\text{-sink})=1

,

p(0\text{-sink})=\infty

2 for $1\leq r\leq n_{s}n_{t}$ do

3

S^{r}(1\text{-sink})=\{\alpha_{\emptyset}\}

,

S^{r}(0\text{-sink})=\emptyset

4

5for $1\leq i\leq 2n$ do

6 for $q\in L_{i}$ do

7

\textup{{estimateAndSample}}(q)

8 if

|S^{r}(q)|\geq\theta

then return

0

9

10

return $\frac{1}{p(q_{\text{source}})}$

To ensure a polynomial running time, approxMCnFBDD_core terminates as soon as the number of samples grows too large (Line 5) and returns $0$ . This output is erroneous but we will show that the probability of terminating this way is negligible. For parameters carefully chosen, approxMCnFBDD_core returns a good estimate of $|B^{-1}(1)|$ with probability larger than $1/2$ . The full FPRAS approxMCnFBDD amplifies this probability to $1-\delta$ by returning the median output of independent runs of approxMCnFBDD.

Algorithm 6

\textup{{approxMCnFBDD}}(B,\varepsilon,\delta)

.

1make

B

alternating,

1

-complete and

0

-reduced

2

n=|var(B)|

,

m=\lceil 8\ln(1/\delta)\rceil

3

\kappa=\varepsilon/(1+\varepsilon)

,

n_{s}=\lceil 4n/\kappa^{2}\rceil

,

n_{t}=\lceil 8\ln(16|B|)\rceil

,

\theta=16n_{s}n_{t}(1+\kappa)|B|

4 for $1\leq j\leq m$ do

5

\mathsf{est}_{j}=\textup{{approxMCnFBDD\_core}}(B,n,n_{s},n_{t},\theta)

6

return

\mathsf{median}(\mathsf{est}_{1},\dots,\mathsf{est}_{m})

5 Derivation paths

Models can have several accepting paths in an nFBDD. For $q$ a node of $B$ and $\alpha\in\mathsf{mod}(q)$ , we map $(\alpha,q)$ to a canonical accepting path, called the derivation path of $\alpha$ for $q$ , denoted by $\mathsf{path}(\alpha,q)$ . A path $\mathcal{P}$ is formally represented with a tuple $(V(\mathcal{P}),E(\mathcal{P}))$ , with $V(\mathcal{P})$ a sequence of vertices and $E(\mathcal{P})$ a sequence of edges.

Definition 3.

For $q\in B$ and $\alpha\in\mathsf{mod}(q)$ , the derivation path $\mathsf{path}(\alpha,q)$ is defined as follows:

$\blacksquare$

If $q$ is the $1$ -sink then $\alpha=\alpha_{\emptyset}$ and the only derivation path is $\mathsf{path}(\alpha_{\emptyset},q)=(\{q\},\emptyset)$ .
$\blacksquare$

If $q=ite(x,q_{1},q_{0})$ , let $\alpha^{\prime}$ be the restriction of $\alpha$ to $var(\alpha)\setminus\{x\}$ , then $V(\mathsf{path}(\alpha,q))=V(\mathsf{path}(\alpha^{\prime},q_{\alpha(x)}))\cdot q$ and $E(\mathsf{path}(\alpha,q))$ is $E(\mathsf{path}(\alpha^{\prime},q_{\alpha(x)}))$ plus the $\alpha(x)$ -edge of $q$ .
$\blacksquare$

If $q=q_{1}\lor\dots\lor q_{k}$ with the children ordering $\mathsf{children}(q)=(q_{1},\dots,q_{k})$ , let $i$ be the smallest integer between $1$ and $k$ such that $\alpha\in\mathsf{mod}(q_{i})$ then $V(\mathsf{path}(\alpha,q))=V(\mathsf{path}(\alpha,q_{i}))\cdot q$ and $E(\mathsf{path}(\alpha,q))$ is $E(\mathsf{path}(\alpha,q_{i}))$ plus the edge between $q_{i}$ and $q$ .

Our algorithm constructs sample sets in a way that respect derivation paths. That is, an assignment $\alpha\in\mathsf{mod}(q)$ may end up in $S^{r}(q)$ only if it is derived through $\mathsf{path}(\alpha,q)$ .

Lemma 4.

Let $q\in B$ and $\alpha\in\mathsf{mod}(q)$ , let $V(\mathsf{path}(\alpha,q))=(q_{0},q_{1},\dots,q_{i-1},q_{i})$ with $q_{0}$ the $1$ -sink and $q_{i}=q$ . For every $j\in[0,i-1]$ , let $\alpha_{j}$ be the restriction of $\alpha$ to $var(q_{j})$ . In a run of approxMCnFBDD_core, $\alpha\in S^{r}(q)$ holds only if $\alpha_{j}\in S^{r}(q_{j})$ holds for every $j\in[0,i-1]$ .

Proof.

$\alpha_{0}=\alpha_{\emptyset}\in S^{r}(1\text{-sink})=S^{r}(q_{0})$ holds by construction. Now consider $j>0$ , it is sufficient to show that $\alpha_{j}\in S^{r}(q_{j})$ only if $\alpha_{j-1}\in S^{r}(q_{j-1})$ .

$\blacksquare$

If $q_{j}=ite(x,q_{j,1},q_{j,0})$ then $\alpha_{j}=\alpha_{j-1}\cup\{x\mapsto\alpha(x)\}$ and $q_{j-1}=q_{j,\alpha(x)}$ . Looking at estimateAndSample for decision nodes, one sees that $\alpha_{j}\in S^{r}(q_{j})$ only if $\alpha_{j-1}\in\textup{{reduce}}(S^{r}(q_{j,\alpha(x)}),p(q_{j})/p(q_{j-1}))$ , so only if $\alpha_{j-1}\in S^{r}(q_{j,\alpha(x)})=S^{r}(q_{j-1})$ .
$\blacksquare$

If $q_{j}$ is a $\lor$ -node with $\mathsf{children}(q_{j})=(q^{0}_{j},\dots,q^{k}_{j})$ then $\alpha_{j}=\alpha_{j-1}$ and there is an $i$ such that $q_{j-1}=q^{i}_{j}$ . Observe that $\alpha_{j}\in S^{r}(q_{j})$ only if $\alpha_{j}\in\hat{S}^{r}(q_{j})$ – so only if $\alpha_{j}$ is $\textup{{reduce}}(S^{r}(q^{\ell}_{j}),\rho/p(q^{\ell}_{j}))$ – for the smallest $\ell$ such that $\alpha_{j}\in\mathsf{mod}(q^{\ell}_{j})$ ; so only if $\alpha_{j}=\alpha_{j-1}\in S^{r}(q^{\ell}_{j})$ . The definition of $\mathsf{path}(\alpha,q)$ implies that $\ell=i$ .

$\hfill\blacktriangleleft$

Given two derivation paths $\mathcal{P}$ and $\mathcal{P}^{\prime}$ . We call their last common prefix nodes denoted by $\mathsf{lcpn}(\mathcal{P},\mathcal{P}^{\prime})$ , the deepest node where the two paths diverge, that is, the first node contained in both paths from which the they follow different edges. Note that if $\mathcal{P}$ and $\mathcal{P}^{\prime}$ are consistent up to node $q^{\prime}$ , and $q=ite(x,q^{\prime},q^{\prime})$ , and $\mathcal{P}$ follows the $0$ -edge while $\mathcal{P}^{\prime}$ follows the $1$ -edge, then the two paths diverge at $q^{\prime}$ even though they both contain $q$ .

Definition 5.

Let $\mathcal{P}=((q_{0},\dots,q_{k}),(e_{1},\dots,e_{k}))$ and $\mathcal{P}^{\prime}=((q^{\prime}_{0},\dots,q^{\prime}_{\ell}),(e^{\prime}_{1}% ,\dots,e^{\prime}_{\ell}))$ be two derivation paths. The last common prefix node, denoted by $\mathsf{lcpn}(\mathcal{P},\mathcal{P}^{\prime})$ , is the node $q_{i}$ for the biggest $i$ such that $(q_{0},\dots,q_{i})=(q^{\prime}_{0},\dots,q^{\prime}_{i})$ and $(e_{1},\dots,e_{i})=(e^{\prime}_{1},\dots,e^{\prime}_{i})$ .

Note that every derivation path contains the $1$ -sink for first node, so the last common prefix node is well-defined. Let $V(\mathsf{path}(\alpha,q))=(q_{0},\dots,q_{i})$ with $q_{0}$ the $1$ -sink and $q_{i}=q$ . For every $0\leq\ell\leq i$ , we define

I(\alpha,q,\ell):=\{\alpha^{\prime}\in\mathsf{mod}(q)\mid\mathsf{lcpn}(\mathsf% {path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q))=q_{\ell}\}.

The following result will play a key role in bounding the variance of estimators in the analysis.

Lemma 6.

Let $\alpha\in\mathsf{mod}(q)$ and $V(\mathsf{path}(\alpha,q))=(q_{0},\dots,q_{i})$ with $q_{0}$ the $1$ -sink and $q_{i}=q$ . For every $0\leq\ell\leq i$ , $|I(\alpha,q,\ell)|\leq\frac{|\mathsf{mod}(q)|}{|\mathsf{mod}(q_{\ell})|}$ .

Proof.

Let $I(\alpha,q,\ell)=\{\alpha^{1},\alpha^{2},\dots\}$ . Let $\alpha_{\ell}$ be the restriction of $\alpha$ to $var(q_{\ell})$ . By definition, every $\alpha^{i}$ is of the form $\alpha_{\ell}\cup\beta^{i}$ for some assignment $\beta^{i}$ to $var(q)\setminus var(q_{\ell})$ . Consider $\alpha^{\prime}_{\ell}\in\mathsf{mod}(q_{\ell})$ , then every $\alpha^{\prime}_{\ell}\cup\beta^{i}$ is in $\mathsf{mod}(q)$ . Since the $\alpha^{i}$ s differ on $var(q)\setminus var(q_{\ell})$ , the $\beta^{i}$ s are pairwise distinct, and therefore $\{\alpha^{\prime}_{\ell}\cup\beta^{i}\}_{i}$ is a set of $|I(\alpha,q,\ell)|$ distinct assignments. Considering all $|\mathsf{mod}(q_{\ell})|$ possible choices for $\alpha^{\prime}_{\ell}$ , we find that $\{\alpha^{\prime}_{\ell}\cup\beta^{i}\}_{\alpha^{\prime}_{\ell},i}$ is a set of $|\mathsf{mod}(q_{\ell})|\cdot|I(\alpha,q,\ell)|$ distinct assignments in $\mathsf{mod}(q)$ . Hence $|\mathsf{mod}(q_{\ell})|\cdot|I(\alpha,q,\ell)|\leq|\mathsf{mod}(q)|$ . $\hfill\blacktriangleleft$

6 The Framework for the Analysis

We introduce a random process that simulates approxMCnFBDD_core. Our intuition is that, for every $\alpha\in\mathsf{mod}(q)$ , a statement in the veins of “ $\Pr[\alpha\in S^{r}(q)]=p(q)$ ” should hold. The problem is that this equality makes no sense because $\Pr[\alpha\in S^{r}(q)]$ is a fixed real value whereas $p(q)$ is a random variable. The variables $S^{r}(q)$ and $p(q)$ for different $q$ are too dependent of each other so we use a random process to work with new variables that behave more nicely. The random process simulates several runs of the algorithm for all possible values of the $p(q)$ s. There, $S^{r}(q)$ is simulated by a different variable for each possible run. A coupling argument then allows us to replace $S^{r}(q)$ by one of these variables assuming enough knowledge on the algorithm run up to $q$ , encoded in what we call a history for $q$ .

6.1 History

A history $h$ for a set of nodes $Q$ is a mapping $h:Q\rightarrow\mathbbm{Q}\cup\{\infty\}.$ $h$ is realizable when there exists a run of $\textup{{approxMCnFBDD\_core}}^{*}$ that gives the value $h(q)$ to $p(q)$ for every $q\in Q$ . Such a run is said compatible with $h$ . Two histories $h$ for $Q$ and $h^{\prime}$ for $Q^{\prime}$ are compatible when $h(q)=h^{\prime}(q)$ for all $q\in Q\cap Q^{\prime}$ . Compatible histories can be merged into an history $h\cup h^{\prime}$ for $Q\cup Q^{\prime}$ . For $q\in Q$ and $t\in\mathbbm{Q}$ , we write $h\cup(q\mapsto t)$ to refer to the history $h$ augmented with $h(q)=t$ . For $q\in B$ , we define the set $\mathsf{desc}(q)$ of its descendants by $\mathsf{desc}(1\text{-sink})=\emptyset$ and $\mathsf{desc}(q)=\mathsf{children}(q)\cup\bigcup_{q^{\prime}\in\mathsf{% children}(q)}\mathsf{desc}(q^{\prime})$ . Note that $q\not\in\mathsf{desc}(q)$ . We only study histories realizable for sets $Q$ that are closed for $\mathsf{desc}$ , that is, if $q\in Q$ and $q^{\prime}$ is a descendant of $q$ , then $q^{\prime}\in Q$ . Thus we abuse terminology and refer to a history for $\mathsf{desc}(q)$ as a history for $q$ . The only history for the sinks is the vacuous history $h_{\emptyset}$ for $Q=\emptyset$ (because no descendants).

6.2 Random Process

The random process comprises $n_{s}n_{t}$ independent copies identified by the superscript $r$ . For $q\in B$ , $t\in\mathbbm{Q}\cup\{\infty\}$ and $h$ a realizable history for $q$ , we have a random variable $\mathfrak{S}^{r}_{h,t}(q)$ whose domain is all possible subsets of $\mathsf{mod}(q)$ . $\mathfrak{S}^{r}_{h,t}(q)$ simulates $S^{r}(q)$ in runs of compatible with $h$ and where the value $t$ is assigned to $p(q)$ .

$\blacksquare$

If $q$ is the $0$ -sink, then $\mathsf{mod}(q)=\emptyset$ and only $\mathfrak{S}^{r}_{h_{\emptyset},\infty}(q)=\emptyset$ is defined.
$\blacksquare$

If $q$ is the $1$ -sink, then $\mathsf{mod}(q)=\{\alpha_{\emptyset}\}$ and only $\mathfrak{S}^{r}_{h_{\emptyset},1}(q)=\{\alpha_{\emptyset}\}$ is defined.
$\blacksquare$

If $q=ite(x,q_{1},q_{0})$ , then for every $\mathfrak{S}^{r}_{h_{0},t_{0}}(q_{0})$ , $\mathfrak{S}^{r}_{h_{1},t_{1}}(q_{1})$ with $h_{1}$ and $h_{0}$ realizable and compatible histories for $q_{1}$ and $q_{0}$ , let $h=h_{1}\cup h_{0}\cup(q_{0}\mapsto t_{0},q_{1}\mapsto t_{1})$ and $t=\left(\frac{1}{t_{0}}+\frac{1}{t_{1}}\right)^{-1}$

$\mathfrak{S}^{r}_{h,t}(q)=\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{0},t_{0}% }(q_{0})\otimes\{x\mapsto 0\},\frac{t}{t_{0}}\right)\cup\textup{{reduce}}\left% (\mathfrak{S}^{r}_{h_{1},t_{1}}(q_{1})\otimes\{x\mapsto 1\},\frac{t}{t_{1}}% \right).$
$\blacksquare$

If $q=q_{1}\lor\dots\lor q_{k}$ then for every $\mathfrak{S}^{r}_{h_{1},t_{1}}(q_{1})$ , $\dots$ , $\mathfrak{S}^{r}_{h_{k},t_{k}}(h_{k})$ with realizable and pairwise compatible histories, we define $h=h_{1}\cup\dots\cup h_{k}\cup(q_{1}\mapsto t_{1},\dots,q_{k}\mapsto t_{k})$ , $t_{\min}=\min(t_{1},\dots,t_{k})$ and the variable $\hat{\mathfrak{S}}^{r}_{h}(q)$ that simulates $\hat{S}^{r}(q)$ when the history for $q$ is $h$

$\hat{\mathfrak{S}}^{r}_{h}(q)=\textup{{union}}\left(q,\textup{{reduce}}\left(% \mathfrak{S}^{r}_{h_{1},t_{1}}(q_{1}),\frac{t_{\min}}{t_{1}}\right),\dots,% \textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{k},t_{k}}(h_{k}),\frac{t_{\min}}{t% _{k}}\right)\right).$

For all $t\leq t_{\min}$ we define $\mathfrak{S}^{r}_{h,t}(q)=\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{h}(q)% ,\frac{t}{t_{\min}}\right).$

We make important observations to motivate the interest of the random process. Let $H(q)$ be the random variable on the history for $q$ obtained when running $\textup{{approxMCnFBDD\_core}}^{*}$ .

Fact 7.

It holds that $(H(q),(\hat{S}^{r}(q)\mid r\in R))=(H(q),(\hat{\mathfrak{S}}^{r}_{H(q)}(q)\mid r% \in R))$ and $(H(q),p(q),(S^{r}(q)\mid r\in R))=(H(q),p(q),(\mathfrak{S}^{r}_{H(q),p(q)}(q))% \mid r\in R))$

Fact 7 is explained in more details in the full version of the paper. The equalities should be interpreted as follows: for every $(A^{r}\subseteq\mathsf{mod}(q)\mid r\in R)$ , the following holds:

		$\displaystyle\Pr\left[H(q)=h,\,p(q)=t,\,\bigcap\nolimits_{r\in R}S^{r}(q)=A^{r% }\right]=\Pr\left[H(q)=h,\,p(q)=t,\,\bigcap\nolimits_{r\in R}\mathfrak{S}^{r}_% {h,t}(q)=A^{r}\right]$
		$\displaystyle\Pr\left[H(q)=h\text{ and }\bigcap\nolimits_{r\in R}\hat{S}^{r}(q% )=A^{r}\right]=\Pr\left[H(q)=h\text{ and }\bigcap\nolimits_{r\in R}\hat{% \mathfrak{S}}^{r}_{h}(q)=A^{r}\right].$

A second key observation is that the variables $\mathfrak{S}^{r}_{h,t}(q)$ and $\hat{\mathfrak{S}}^{r}_{h}(q)$ are independent of $H(q)$ , $p(q)$ , $S^{r}(q)$ and $\hat{S}^{r}(q)$ . This is because the latter variables comes from the algorithm while the former are defined within the random process, and the two do not interact in any way.

Fact 8.

The variables $\mathfrak{S}^{r}_{h,t}(q)$ and $\hat{\mathfrak{S}}^{r}_{h}(q)$ are independent of any combination of $H(q^{\prime})$ , $p(q^{\prime})$ , $S^{r}(q^{\prime})$ and $\hat{S}^{r}(q^{\prime})$ for every $q^{\prime}$ (including $q^{\prime}=q$ ).

In the random process we have the correct variant of the equality “ $\Pr[\alpha\in S^{r}(q)]=p(q)$ ”.

Lemma 9.

For every $\mathfrak{S}^{r}_{h,t}(q)$ and $\alpha\in\mathsf{mod}(q)$ , it holds that $\Pr[\alpha\in\mathfrak{S}^{r}_{h,t}(q)]=t$ . In addition, if $q$ is a $\lor$ -node with $\mathsf{children}(q)=(q_{1},\dots,q_{k})$ then $\Pr[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)]=\min(h(q_{1}),\dots,h(q_{k}))$ .

Lemma 10.

For every $\mathfrak{S}^{r}_{h,t}(q)$ with $\mathsf{children}(q)=(q_{1},\dots,q_{k})$ and $\alpha,\alpha^{\prime}\in\mathsf{mod}(q)$ with $\alpha\neq\alpha^{\prime}$ , let $t^{*}=h(\mathsf{lcpn}(\mathsf{path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q))$ , then we have that $\Pr[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\mid\alpha^{\prime}\in\mathfrak{S}^{r}_{% h,t}(q)]\leq\frac{t}{t^{*}}$ and if $q$ is $\lor$ -node then $\Pr[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\mid\alpha^{\prime}\in\hat{\mathfrak% {S}}^{r}_{h}(q)]\leq\frac{\min(h(q_{1}),\dots,h(q_{k}))}{t^{*}}.$

Lemmas 9 and 10 are proved in appendix. Compared to “ $\Pr[\alpha\in S^{r}(q)]=p(q)$ ”, there is nothing wrong with the lemmas as $t$ , $t^{\prime}$ and the $h(q_{i})$ s are fixed real numbers.

7 Analysis

We now conduct the analysis of approxMCnFBDD. The hardest part to analyze is the core algorithm approxMCnFBDD_core, for which we will prove the following.

Lemma 11.

Let $B$ be a $1$ -complete $0$ -reduced and alternating nFBDD over $n$ variables. Let $m=\max_{i}|L^{i}|$ , $\varepsilon>0$ , and $\kappa=\frac{\varepsilon}{1+\varepsilon}$ . If $n_{s}\geq\frac{4n}{\kappa^{2}}$ , $n_{t}\geq 8\ln(16|B|)$ and $\theta=16n_{s}n_{t}(1+\kappa)|B|$ then $\textup{{approxMCnFBDD\_core}}(B,n,n_{s},n_{t},\theta)$ runs in time $O(n_{s}n_{t}\log(n_{t})\cdot\theta\cdot|B|^{2})$ and returns $\mathsf{est}$ with the guarantee $\Pr\left[\mathsf{est}\notin(1\pm\varepsilon)|B^{-1}(1)|\right]\leq\frac{1}{4}.$

Our main result is obtained decreasing this $1/4$ down to any $\delta>0$ with the median technique.

See 1

Proof.

Let $\mathsf{est}_{1},\dots,\mathsf{est}_{m}$ be the estimates from $m$ independent calls to approxMCnFBDD_core. Let $X_{i}$ be the indicator variable that takes value $1$ if and only if $\mathsf{est}_{i}\not\in(1\pm\varepsilon)|B^{-1}(1)|$ , and define $\bar{X}=X_{1}+\dots+X_{m}$ . By Lemma 11, $\textsf{E}[\bar{X}]\leq m/4$ . Hoeffding bound gives

\Pr\Big{[}\underset{1\leq i\leq m}{\mathsf{median}(X_{i})}\not\in(1\pm% \varepsilon)|B^{-1}(1)|\Big{]}=\Pr\left[\bar{X}>\frac{m}{2}\right]\leq\Pr\left% [\bar{X}-\textsf{E}[\bar{X}]>\frac{m}{4}\right]\leq e^{-m/8}\leq\delta.

The running time is $O(|\log(\frac{1}{\delta})|)$ times that of $\textup{{approxMCnFBDD\_core}}(B^{\prime},n,n_{s},n_{t})$ where $B^{\prime}$ is $B$ after it has been made $1$ -complete, $0$ -reduced, and alternating. By Lemma 2, $|B^{\prime}|=O(n|B|^{2})$ and $B^{\prime}$ is constructed in time $O(n|B|^{2})$ . So each call to $\textup{{approxMCnFBDD\_core}}(B^{\prime},n,$ $n_{s},n_{t})$ takes time $O(n^{5}|B|^{6}\log|B|\varepsilon^{-4})$ $\hfill\blacktriangleleft$

Recall that $\textup{{approxMCnFBDD\_core}}^{*}$ is approxMCnFBDD_core without the terminating condition of Line 5, that is, where the sets $S^{r}(q)$ can grow big. Analyzing $\textup{{approxMCnFBDD\_core}}^{*}$ is enough to prove Lemma 11 without running time requirements. In particular, it is enough to prove Lemmas 12 and 13. For these lemmas the settings described in Lemma 11 are assumed.

Lemma 12.

The probability that $\textup{{approxMCnFBDD\_core}}^{*}(B,n,n_{s},n_{t},\theta)$ computes $p(q)\not\in(1\pm\kappa)|\mathsf{mod}(q)|^{-1}$ for some $q\in B$ is at most $1/8$ .

Lemma 13.

The probability that $\textup{{approxMCnFBDD\_core}}^{*}(B,n,n_{s},n_{t},\theta)$ constructs sets $S^{r}(q)$ such that $|S^{r}(q)|\geq\theta$ for some $q\in B$ is at most $1/8$ .

Proof of Lemma 11.

Let $\texttt{A}^{(\ast)}=\textup{{approxMCnFBDD\_core}}^{(\ast)}(B,n,n_{s},n_{t},\theta)$ .

	$\displaystyle\Pr_{\texttt{A}}$	$\displaystyle\left[\mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(1)\|\right]$
		$\displaystyle=\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\bigcap_{r,q}\|S^{r}(q)\|<\theta\text{ and }% \mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(1)\|\right]$
		$\displaystyle\leq\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(% 1)\|\right]$
		$\displaystyle\leq\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\bigcup_{q}p(q)\not\in\frac{1}{(1\pm% \varepsilon)\|\mathsf{mod}(q)\|}\right]$

where $q$ ranges over $B$ ’s nodes and $r$ ranges in $[n_{s}n_{t}]$ . The parameter $\kappa$ has been set so that $p(q)\not\in\frac{1\pm\kappa}{|\mathsf{mod}(q)|}$ implies $p(q)\not\in\frac{1}{(1\pm\varepsilon)|\mathsf{mod}(q)|}$ so, using Lemmas 12 and 13:

\Pr_{\texttt{A}}\left[\mathsf{est}\not\in(1\pm\varepsilon)|B^{-1}(1)|\right]% \leq\Pr_{\texttt{A}^{*}}\left[\bigcup_{r,q}|S^{r}(q)|\geq\theta\right]+\Pr_{% \texttt{A}^{*}}\left[\bigcup_{q}p(q)\not\in\frac{1\pm\kappa}{|\mathsf{mod}(q)|% }\right]\leq\frac{1}{4}

The algorithm stops whenever the number of samples grows beyond $\theta$ so, for the worst-case running time, the number of samples is less than $\theta$ . Each node goes once through estimateAndSample. For a decision node, estimateAndSample takes time $O(n_{s}n_{t}\theta)$ . For a $\lor$ -node $q$ , estimateAndSample calls union $n_{s}n_{t}$ times, does a median of means where it computes the median of $n_{t}$ means of $n_{s}$ integers, and updates the sample sets. Updating the sample sets takes time $O(n_{s}n_{t}\theta)$ . Each mean costs $O(n_{s})$ and the median requires sorting so the whole thing is done in $O(n_{s}n_{t}\log(n_{t}))$ time. For each sample, the union tests whether it is a model of the children of $q$ , model checking is a linear-time operation on nFBDD so the total cost of one union is $O(|\mathsf{children}(q)|\cdot|B|\cdot\theta)$ . So the total cost of estimateAndSample for all $\lor$ -nodes is at most $O(n_{s}n_{t}\log(n_{t})\cdot\theta\cdot|B|\cdot\sum_{q}|\mathsf{children}(q)|)% =O(n_{s}n_{t}\log(n_{t})\cdot\theta\cdot|B|^{2})$ . $\hfill\blacktriangleleft$

It remains to prove Lemmas 12 and 13.

7.1 Proof of Lemma 12

Let $\Delta(q)$ be the interval $\frac{1\pm\kappa}{|\mathsf{mod}(q)|}$ and $\nabla(q)$ be the interval $\frac{|\mathsf{mod}(q)|}{1\pm\kappa}$ .

Claim 14.

The event $\bigcup_{q\in B}\left(p(q)\not\in\Delta(q)\right)$ occurs if and only if the event
$\bigcup_{q\in L_{>0}}\left(p(q)\not\in\Delta(q)\text{ and for all }q^{\prime}% \in\mathsf{desc}(q),\,p(q^{\prime})\in\Delta(q^{\prime})\right)$ occurs.

Proof.

The “if” direction is trivial. For the other direction, suppose that $p(q)\not\in\Delta(q)$ holds for some $q$ . Let $i$ be the smallest integer such that there is $q\in L_{i}$ and $p(q)\not\in\Delta(q)$ . $i$ cannot be $0$ because the only node in $L_{0}$ is the $1$ -sink and $p(1\text{-sink})=1=|\mathsf{mod}(1\text{-sink})|^{-1}\in\Delta(1\text{-sink})$ . So $q\in L_{>0}$ and, by minimality of $i$ , we have that $p(q^{\prime})\in\Delta(q^{\prime})$ for all $q^{\prime}\in\mathsf{desc}(q)$ . $\hfill\vartriangleleft$

	$\displaystyle\Pr\bigg{[}\bigcup_{q\in B}p(q)\not\in\Delta(q)\bigg{]}=$	$\displaystyle\Pr\bigg{[}\bigcup_{q\in L_{>0}}p(q)\not\in\Delta(q)\text{ and }% \forall q^{\prime}\in\mathsf{desc}(q),\,p(q^{\prime})\in\Delta(q^{\prime})% \bigg{]}$		(1)
	$\displaystyle\leq$	$\displaystyle\sum_{q\in L_{>0}}\underbrace{\Pr\left[p(q)\not\in\Delta(q)\text{% and }\forall q^{\prime}\in\mathsf{desc}(q),\,p(q^{\prime})\in\Delta(q^{\prime% })\right]}_{P(q)}.$		(1)

We bound $P(q)$ from above. If $q=ite(x,q_{1},q_{0})$ is a decision node, then by construction, $p(q_{0})\in\Delta(q_{0})$ and $p(q_{1})\in\Delta(q_{1})$ implies $p(q)^{-1}\in\frac{|\mathsf{mod}(q_{0})|+|\mathsf{mod}(q_{1})|}{1\pm\kappa}=% \frac{|\mathsf{mod}(q)|}{1\pm\kappa}=\nabla(q)$ with probability $1$ . Thus $P(q)=0$ for decision nodes and only the case of $\lor$ -nodes remains.

Going to the random process

To bound $P(q)$ when $q$ is a $\lor$ -node, we move the analysis to the random process, whose variables we can analyze using Lemmas 9 and 10. Consider the set $\mathcal{H}_{q}$ of realizable histories for $q$ and denote by $H(q)=h$ the event that the algorithm sets $p(q^{\prime})$ to $h(q^{\prime})$ for all $q^{\prime}\in\mathsf{desc}(q)$ .

	$\displaystyle P(q)$	$\displaystyle=\Pr\bigg{[}\bigcup_{h\in\mathcal{H}_{q}}H(q)=h\text{ and }p(q)% \not\in\Delta(q)\text{ and for all }q^{\prime}\in\mathsf{desc}(q),\,p(q^{% \prime})\in\Delta(q^{\prime})\bigg{]}$
		$\displaystyle\leq\sum_{h\in\mathcal{H}_{q}}\Pr\left[H(q)=h\text{ and }p(q)\not% \in\Delta(q)\text{ and for all }q^{\prime}\in\mathsf{desc}(q),\,p(q^{\prime})% \in\Delta(q^{\prime})\right]$

Let $\mathcal{H}^{*}_{q}$ be the subset of $\mathcal{H}_{q}$ where $h(q^{\prime})\in\Delta(q^{\prime})$ holds for every $q^{\prime}\in\mathsf{desc}(q)$ , then

	$\displaystyle P(q)$	$\displaystyle\leq\sum_{h\in\mathcal{H}^{*}_{q}}\Pr\left[H(q)=h\text{ and }p(q)% \not\in\Delta(q)\text{ and for all }q^{\prime}\in\mathsf{desc}(q),\,p(q^{% \prime})\in\Delta(q^{\prime})\right]$
		$\displaystyle=\sum_{h\in\mathcal{H}^{*}_{q}}\Pr\left[H(q)=h\text{ and }p(q)% \not\in\Delta(q)\right].$

Let $\rho=\min(p(q_{1}),\dots,p(q_{k}))$ , $\rho_{h}=\min(h(q_{1}),\dots,h(q_{k}))$ and $M_{j}=\frac{1}{\rho\cdot n_{s}}\sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}|\hat{S}^{r% }(q)|$ . Note that $\rho$ is a random variable whereas $\rho_{h}$ is a constant. If $H(q)=h$ then the events $\rho=\rho_{h}$ and $p(q)=\min(\rho_{h},\hat{\rho})$ both hold, where $\hat{\rho}=\mathsf{median}(M_{0},\dots,M_{n_{t}-1})^{-1}$ .

Claim 15.

If $H(q)=h$ then $\hat{\rho}\in\Delta(q)$ implies that $p(q)\in\Delta(q)$ .

Proof.

$H(q)=h$ implies $p(q)=\min(\rho_{h},\hat{\rho})$ . If $p(q)=\hat{\rho}$ holds then, trivially, $\hat{\rho}\in\Delta(q)$ implies that $p(q)\in\Delta(q)$ . If $p(q)=\rho_{h}$ occurs then $\hat{\rho}\in\Delta(q)$ implies that $p(q)\leq\hat{\rho}\leq\frac{1+\kappa}{|\mathsf{mod}(q)|}$ and, since $h\in\mathcal{H}^{*}_{q}$ guarantees that $\rho_{h}\geq\frac{1-\kappa}{\max_{j\in[k]}|\mathsf{mod}(q_{j})|}\geq\frac{1-% \kappa}{|\mathsf{mod}(q)|}$ , we have that $p(q)\in\Delta(q)$ . $\hfill\vartriangleleft$ Let $\mathfrak{M}_{j,h}=\frac{1}{\rho_{h}n_{s}}\sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}% |\hat{\mathfrak{S}}^{r}_{h}(q)|$ . Using that $H(q)=h$ implies $\rho=\rho_{h}$ and Fact 7, we find that $(H(q),\mathsf{median}_{j}(M_{j}))=(H(q),\mathsf{median}_{j}(\mathfrak{M}_{j,H(% q)}))$ .

$\displaystyle\Pr$	$\displaystyle\left[H(q)=h\text{ and }p(q)\not\in\Delta(q)\right]\leq\Pr\left[H% (q)=h\text{ and }\hat{\rho}\not\in\Delta(q)\right]$	(Claim 15)
	$\displaystyle=\Pr\left[H(q)=h\text{ and }{\mathsf{median}}_{0\leq j<n_{t}}(M_{% j})\not\in\nabla(q)\right]$	(by definition of $\hat{\rho}$ )
	$\displaystyle\leq\Pr\left[H(q)=h\text{ and }{\mathsf{median}}_{0\leq j<n_{t}}(% \mathfrak{M}_{j,h})\not\in\nabla(q)\right]$	(Fact 7)
	$\displaystyle=\Pr[H(q)=h]\Pr\left[{\mathsf{median}}_{0\leq j<n_{t}}(\mathfrak{% M}_{j,h})\not\in\nabla(q)\right]$	(Fact 8)

We have reached our goal to replace variables by their counterpart in the random process. Now we bound $\Pr\left[\mathsf{median}_{j}(\mathfrak{M}_{j,h})\not\in\nabla(q)\right]$ using Chebyshev’s inequality and Hoeffding bound.

Variance upper bound

By Lemma 9, the expected value of $|\hat{\mathfrak{S}}^{r}_{h}(q)|$ is $\mu=\rho_{h}|\mathsf{mod}(q)|$ . Now for the variance,

$\displaystyle\textsf{Var}\left[\|\hat{\mathfrak{S}}^{r}_{h}(q)\|\right]$	$\displaystyle\leq\textsf{E}\left[\|\hat{\mathfrak{S}}^{r}_{h}(q)\|^{2}\right]=% \mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in\mathsf{mod}(q)\\ \alpha\neq\alpha^{\prime}\end{subarray}}\Pr\left[\alpha\in\hat{\mathfrak{S}}^{% r}_{h}(q)\text{ and }\alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]$
	$\displaystyle=\mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in\mathsf{% mod}(q)\\ \alpha\neq\alpha^{\prime}\end{subarray}}\Pr\left[\alpha\in\hat{\mathfrak{S}}^{% r}_{h}(q)\mid\alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]\Pr\left[% \alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]$
	$\displaystyle\leq\mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in\mathsf% {mod}(q)\\ \alpha\neq\alpha^{\prime}\end{subarray}}\frac{\rho_{h}^{2}}{h(\mathsf{lcpn}(% \mathsf{path}(q,\alpha),\mathsf{path}(q,\alpha^{\prime}))}$	(Lemmas 9 and 10)

Let $\mathcal{P}=\mathsf{path}(\alpha,q)$ and $V(\mathcal{P})=(q^{0}_{\alpha},q^{1}_{\alpha},q^{2}_{\alpha},\dots,q^{i-1}_{% \alpha},q)$ , with $q^{0}_{\alpha}=1\text{-sink}$ . Let $\mathcal{P}^{\prime}=\mathsf{path}(\alpha^{\prime},q)$ for any $\alpha^{\prime}\in\mathsf{mod}(q)$ distinct from $\alpha$ . Then $\mathsf{lcpn}(\mathcal{P},\mathcal{P}^{\prime})$ is one of the $q^{j}_{\alpha}$ . Recall that $I(\alpha,q,j)$ is the set of $\alpha^{\prime}\in\mathsf{mod}(q)$ such that $\mathsf{lcpn}(\mathcal{P},\mathcal{P}^{\prime})=q^{j}_{\alpha}$ .

	$\displaystyle\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in\mathsf{mod}(q)% \\ \alpha\neq\alpha^{\prime}\end{subarray}}\frac{\rho_{h}^{2}}{h(\mathsf{lcpn}(% \mathsf{path}(q,\alpha),\mathsf{path}(q,\alpha^{\prime}))}=\sum_{\alpha\in% \mathsf{mod}(q)}\sum_{j\in[0,i-1]}\|I(\alpha,q,j)\|\frac{\rho_{h}^{2}}{h(q^{j}_{% \alpha})}$
	$\displaystyle\leq\sum_{\alpha\in\mathsf{mod}(q)}\sum_{j\in[0,i-1]}\frac{\rho_{% h}^{2}\|\mathsf{mod}(q)\|}{\|\mathsf{mod}(q^{j}_{\alpha})\|\cdot h(q^{j}_{\alpha})}\qquad$		(Lemma 6)

Because $h\in\mathcal{H}^{*}_{q}$ and $h(q^{j}_{\alpha})$ is in $\Delta(q^{j}_{\alpha})$ we have $|\mathsf{mod}(q^{j}_{\alpha})|\cdot h(q^{j}_{\alpha})\geq 1-\kappa$ .

\displaystyle\sum_{\alpha\in\mathsf{mod}(q)}\sum_{j\in[0,i-1]}\frac{\rho_{h}^{% 2}|\mathsf{mod}(q)|}{|\mathsf{mod}(q^{j}_{\alpha})|\cdot h(q^{j}_{\alpha})}

\displaystyle\leq\frac{\rho_{h}^{2}}{1-\kappa}\sum_{\alpha\in\mathsf{mod}(q)}% \sum_{j\in[0,i-1]}|\mathsf{mod}(q)|\leq\frac{\mu^{2}n}{1-\kappa}

Putting everything together, we conclude that $\textsf{Var}[|\hat{\mathfrak{S}}^{r}_{h}(q)|]\leq\mu+\frac{\mu^{2}n}{1-\kappa}.$

Median of means

We have that $\textsf{E}[\mathfrak{M}_{j,h}]=\frac{\mu}{\rho_{h}}=|\mathsf{mod}(q)|$ and, by independence of the variables $\{\hat{\mathfrak{S}}^{r}_{h}(q)\}_{r}$

\textsf{Var}[\mathfrak{M}_{j,h}]=\sum_{r=j\cdot n_{s}+1}^{(j+1)n_{s}}\frac{% \textsf{Var}[|\hat{\mathfrak{S}}^{r}_{h}(q)|]}{\rho_{h}^{2}n_{s}^{2}}\leq\frac% {1}{\rho_{h}^{2}n_{s}}\left(\mu+\frac{\mu^{2}n}{1-\kappa}\right)=\frac{1}{n_{s% }}\left(\frac{|\mathsf{mod}(q)|}{\rho_{h}}+\frac{n|\mathsf{mod}(q)|^{2}}{1-% \kappa}\right).

$\mathfrak{M}_{j,h}\in\frac{|\mathsf{mod}(q)|}{1\pm\kappa}$ occurs if and only if $\frac{-\kappa|\mathsf{mod}(q)|}{1+\kappa}\leq\mathfrak{M}_{j,h}-|\mathsf{mod}(% q)|\leq\frac{\kappa|\mathsf{mod}(q)|}{1-\kappa}$ , which is subsumed by $|\mathfrak{M}_{j,h}-|\mathsf{mod}(q)||\leq\frac{\kappa|\mathsf{mod}(q)|}{1+\kappa}$ . So Chebyshev’s inequality gives

$\displaystyle\Pr$	$\displaystyle\left[\mathfrak{M}_{j,h}\notin\frac{\|\mathsf{mod}(q)\|}{1\pm\kappa% }\right]\leq\Pr\left[\big{\|}\mathfrak{M}_{j,h}-\|\mathsf{mod}(q)\|\big{\|}>\frac{% \kappa\|\mathsf{mod}(q)\|}{1+\kappa}\right]\leq\frac{(1+\kappa)^{2}}{\kappa^{2}\|% \mathsf{mod}(q)\|^{2}}\textsf{Var}\left[\mathfrak{M}_{j,h}\right]$
	$\displaystyle\leq\frac{(1+\kappa)^{2}}{\kappa^{2}n_{s}}\left(\frac{1}{\|\mathsf% {mod}(q)\|\rho_{h}}+\frac{n}{1-\kappa}\right)$
	$\displaystyle\leq\frac{(1+\kappa)^{2}}{\kappa^{2}n_{s}}\left(\frac{1}{1-\kappa% }+\frac{n}{1-\kappa}\right)$	( $\rho_{h}\geq\frac{1-\kappa}{\max_{j}\|\mathsf{mod}(q_{j})\|}\geq\frac{1-\kappa}{% \|\mathsf{mod}(q)\|}$ )
	$\displaystyle\leq\frac{2n}{\kappa^{2}n_{s}}\leq\frac{1}{4}$	( $\frac{(1+\kappa)^{2}}{1-\kappa}$ decreases to 1 and $n_{s}\geq\frac{4n}{\kappa^{2}}$ )

By taking the median, we decrease the $\frac{1}{4}$ upper bound to a much smaller value. Let $E_{j}$ be the indicator variable taking value $1$ if and only if $\mathfrak{M}_{j,h}\not\in\frac{|\mathsf{mod}(q)|}{1\pm\kappa}$ and let $\bar{E}=\sum_{j=0}^{n_{t}-1}E_{j}$ . We have $\textsf{E}[\bar{E}]\leq\frac{n_{t}}{4}$ so Hoeffding bound gives

\displaystyle\Pr\left[\underset{0\leq j<n_{t}}{\mathsf{median}}(\mathfrak{M}_{% j,h})\not\in\frac{|\mathsf{mod}(q)|}{1\pm\kappa}\right]=\Pr\left[\bar{E}>\frac% {n_{t}}{2}\right]\leq\Pr\left[\bar{E}-\textsf{E}(\bar{E})\geq\frac{n_{t}}{4}% \right]\leq e^{-n_{t}/8}\leq\frac{1}{16|B|}

where the last inequality comes from $n_{t}\geq 8\ln(16|B|)$ . Putting everything together we have

\displaystyle P(q)\leq\sum_{h\in\mathcal{H}^{*}_{q}}\frac{1}{16|B|}\Pr[H(q)=h]% \leq\frac{1}{16|B|}.

Used in (1), this gives $\Pr\left[\bigcup_{q\in B}p(q)\not\in\Delta(q)\right]\leq\frac{1}{16}$ , thus finishing the proof of Lemma 12. We have shown a $\frac{1}{16}$ bound instead of a $\frac{1}{8}$ bound in preparation for the proof of Lemma 13.

7.2 Proof of Lemma 13

We first bound $\Pr\left[\bigcup_{r,q}|S^{r}(q)|\geq\theta\right]$ from above by

\displaystyle\underbrace{\Pr\left[\bigcup_{r,q}|S^{r}(q)|\geq\theta\text{ and % }\bigcap_{q^{\prime}\in B}p(q^{\prime})\in\frac{1\pm\kappa}{|\mathsf{mod}(q^{% \prime})|}\right]}_{P_{1}}+\underbrace{\Pr\left[\bigcup_{q^{\prime}\in B}p(q^{% \prime})\not\in\frac{1\pm\kappa}{|\mathsf{mod}(q^{\prime})|}\right]}_{P_{2}}.

We have already a $\frac{1}{16}$ upper bound on $P_{2}$ , so we focus on $P_{1}$ .

$\displaystyle P_{1}$	$\displaystyle\leq\sum_{r,q}\Pr\bigg{[}\|S^{r}(q)\|\geq\theta\text{ and }\bigcap_% {q^{\prime}\in B}p(q^{\prime})\in\Delta(q^{\prime})\bigg{]}$	(Union bound)
	$\displaystyle\leq\frac{1}{\theta}\cdot\sum_{r,q}\textsf{E}\bigg{[}\|S^{r}(q)\|% \cdot\prod_{q^{\prime}\in B}\mathbbm{1}\left(p(q^{\prime})\in\Delta(q^{\prime}% )\right)\bigg{]}$	(Markov’s inequality)
	$\displaystyle\leq\frac{1}{\theta}\cdot\sum_{r,q}\underbrace{\textsf{E}\left[\|S% ^{r}(q)\|\cdot\mathbbm{1}\left(p(q)\in\Delta(q)\right)\right]}_{E(r,q)}$

To bound $E(r,q)$ we introduce the history of $q$ and move to the variables of the random process. Recall that $\mathcal{H}_{q}$ is the set of all realizable histories for $q$ .

$\displaystyle E(r,q)$	$\displaystyle=\sum_{t\in\Delta(q)}\textsf{E}\left[\|S^{r}(q)\|\cdot\mathbbm{1}(p% (q)=t)\right]=\sum_{h\in\mathcal{H}_{q}}\sum_{t\in\Delta(q)}\textsf{E}\left[\|S% ^{r}(q)\|\cdot\mathbbm{1}(p(q)=t\text{ and }H(q)=h)\right]$
	$\displaystyle=\sum_{h\in\mathcal{H}_{q}}\sum_{t\in\Delta(q)}\textsf{E}\left[\|% \mathfrak{S}^{r}_{h,t}(q)\|\cdot\mathbbm{1}(p(q)=t\text{ and }H(q)=h)\right]$	(Fact 7)
	$\displaystyle=\sum_{h\in\mathcal{H}_{q}}\sum_{t\in\Delta(q)}\textsf{E}\left[\|% \mathfrak{S}^{r}_{h,t}(q)\|\right]\cdot\Pr[p(q)=t\text{ and }H(q)=h]$	(Fact 8)
	$\displaystyle=\sum_{h\in\mathcal{H}_{q}}\sum_{t\in\Delta(q)}t\cdot\|\mathsf{mod% }(q)\|\cdot\Pr[p(q)=t\text{ and }H(q)=h]$	(Lemma 9)
	$\displaystyle\leq\sum_{h\in\mathcal{H}_{q}}\sum_{t\in\Delta(q)}(1+\kappa)\cdot% \Pr[p(q)=t\text{ and }H(q)=h]\leq(1+\kappa)$	( $t\leq\frac{1+\kappa}{\|\mathsf{mod}(q)\|}$ )

It follows that $P_{1}\leq\frac{(1+\kappa)n_{s}n_{t}|B|}{\theta}\leq\frac{1}{16}$ (because $\theta\geq 16(1+\kappa)n_{s}n_{t}|B|$ ) and therefore $\Pr\left[\bigcup_{r,q}|S^{r}(q)|\geq\theta\right]\leq\frac{1}{16}+\frac{1}{16}% =\frac{1}{8}$ . This finishes the proof of Lemma 13.

8 Conclusion

In this paper, we resolved the open problem of designing an FPRAS for #nFBDD. Our work also introduces a new technique to quantify dependence, and it would be interesting to extend this technique to other languages that generalize nFBDD. Another promising direction for future work would be to improve the complexity of the proposed FPRAS to enable practical adoption.

References

[1] Antoine Amarilli, Marcelo Arenas, YooJung Choi, Mikaël Monet, Guy Van den Broeck, and Benjie Wang. A circus of circuits: Connections between decision diagrams, circuits, and automata. arXiv preprint arXiv:2404.09674, 2024. doi:10.48550/arXiv.2404.09674.
[2] Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. SIGMOD Rec., 53(2):6–20, 2024. doi:10.1145/3685980.3685982.
[3] Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. ACM SIGMOD Record, 53(2):6–20, 2024. doi:10.1145/3685980.3685982.
[4] Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory Comput. Syst., 64(5):861–914, 2020. doi:10.1007/S00224-019-09930-2.
[5] Antoine Amarilli, Timothy van Bremen, and Kuldeep S Meel. Conjunctive queries on probabilistic graphs: The limits of approximability. In 27th International Conference on Database Theory, 2024.
[6] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. Efficient logspace classes for enumeration, counting, and uniform generation. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, pages 59–73. ACM, 2019. doi:10.1145/3294052.3319704.
[7] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. When is approximate counting for conjunctive queries tractable? In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1015–1027. ACM, 2021. doi:10.1145/3406325.3451014.
[8] Paul Beame and Vincent Liew. New limits for knowledge compilation and applications to exact model counting. arXiv preprint arXiv:1506.02639, 2015. arXiv:1506.02639.
[9] Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Trans. Computers, 35(8):677–691, 1986. doi:10.1109/TC.1986.1676819.
[10] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. J. Artif. Intell. Res., 17:229–264, 2002. doi:10.1613/JAIR.989.
[11] Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet. Computing the shapley value of facts in query answering. In SIGMOD ’22: International Conference on Management of Data, pages 1570–1583. ACM, 2022. doi:10.1145/3514221.3517912.
[12] Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Inf. Comput., 134(1):59–74, 1997. doi:10.1006/INCO.1997.2621.
[13] Abhay Kumar Jha and Dan Suciu. On the tractability of query compilation and bounded treewidth. In 15th International Conference on Database Theory, ICDT ’12, pages 249–261. ACM, 2012. doi:10.1145/2274576.2274603.
[14] Abhay Kumar Jha and Dan Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst., 52(3):403–440, 2013. doi:10.1007/S00224-012-9392-5.
[15] Sheldon B. Akers Jr. Binary decision diagrams. IEEE Trans. Computers, 27(6):509–516, 1978. doi:10.1109/TC.1978.1675141.
[16] Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. Counting and random generation of strings in regular languages. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 551–557. ACM/SIAM, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313803.
[17] Richard M. Karp and Michael Luby. Monte-carlo algorithms for enumeration and reliability problems. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 56–64. IEEE Computer Society, 1983. doi:10.1109/SFCS.1983.35.
[18] Kuldeep S. Meel, Sourav Chakraborty, and Umang Mathur. A faster FPRAS for #nfa. Proc. ACM Manag. Data, 2(2):112, 2024. doi:10.1145/3651613.
[19] Stefan Mengel. Counting, Knowledge Compilation and Applications. PhD thesis, Université d’Artois, 2021.
[20] Mikaël Monet. Solving a special case of the intensional vs extensional conjecture in probabilistic databases. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, pages 149–163. ACM, 2020. doi:10.1145/3375395.3387642.
[21] Mikaël Monet and Dan Olteanu. Towards deterministic decomposable circuits for safe queries. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 2100 of CEUR Workshop Proceedings. CEUR-WS.org, 2018. URL: https://ceur-ws.org/Vol-2100/paper19.pdf.
[22] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410–421, 1979. doi:10.1137/0208032.
[23] Ingo Wegener. Branching Programs and Binary Decision Diagrams. SIAM, 2000. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bdd/.

Appendix A Appendix

See 9

Proof.

Let $q\in L_{i}$ . We proceed by induction on $i$ . The base case $i=0$ is immediate since $\mathfrak{S}^{r}_{h_{\emptyset},1}(1\text{-sink})=\{\alpha_{\emptyset}\}$ and $\mathfrak{S}^{r}_{h_{\emptyset},\emptyset}(0\text{-sink})=\emptyset$ are the only variables for $L_{0}$ (and $\frac{1}{\infty}=0$ by definition). Now let $i>0$ , $q\in L_{i}$ , and suppose that the statement holds for all $\mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})$ and $\alpha^{\prime}\in\mathsf{mod}(q^{\prime})$ with $q^{\prime}\in L_{<i}$ . If $i$ is odd then $q$ is a decision node $ite(x,q_{1},q_{0})$ with $q_{0}$ and $q_{1}$ in $L_{i-1}$ (because $B$ is alternating). Let $b=\alpha(x)$ and let $\alpha^{\prime}$ be the restriction of $\alpha$ to $var(\alpha)\setminus\{x\}$ . Then, by induction,

	$\displaystyle\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\right]=\Pr\left[% \alpha\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b}),\frac{t}% {t_{b}}\right)\otimes\{x\mapsto b\}\right]$
	$\displaystyle=\Pr\left[\alpha^{\prime}\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})% \right]\Pr\left[\alpha^{\prime}\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{% b},t_{b}}(q_{b}),\frac{t}{t_{b}}\right)\Big{\|}\,\alpha^{\prime}\in\mathfrak{S}% ^{r}_{h_{b},t_{b}}(q_{b})\right]=t_{b}\cdot\frac{t}{t_{b}}=t$

Now if $i$ is even then $q$ is a $\lor$ -node with children $\mathsf{children}(q)=(q_{1},\dots,q_{k})$ all in $L_{i-1}$ . Let $j$ be the smallest integer such that $\alpha\in\mathsf{mod}(q_{j})$ and let $t_{\min}=\min(h(q_{1}),\dots,h(q_{k}))$ . Then

	$\displaystyle\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]=\Pr\left[% \alpha\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{j},t_{j}}(q_{j}),\frac{t_% {\min}}{t_{j}}\right)\right]=\Pr\left[\alpha\in\mathfrak{S}^{r}_{h_{j},t_{j}}(% q_{j})\right]$
	$\displaystyle\cdot\Pr\left[\alpha\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h% _{j},t_{j}}(q_{j}),\frac{t_{\min}}{t_{j}}\right)\Big{\|}\,\alpha\in\mathfrak{S}% ^{r}_{h_{j},t_{j}}(q_{j})\right]=t_{j}\cdot\frac{t_{\min}}{t_{j}}=t_{\min}$

And for $t\leq t_{\min}$ we have that $\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\right]=\Pr\left[\alpha\in\textup{{% reduce}}\left(\hat{\mathfrak{S}}^{r}_{h}(q),\frac{t}{t_{\min}}\right)\right]$

\displaystyle=\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]\Pr\left[% \alpha\in\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{h}(q),\frac{t}{t_{\min% }}\right)\Big{|}\,\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]=t_{\min}\cdot% \frac{t}{t_{\min}}=t

$\hfill\blacktriangleleft$

See 10

Proof.

We are going to prove a stronger statement, namely, that for every $i$ , for every $q$ and $q^{\prime}$ (potentially $q=q^{\prime}$ ) in $L_{i}$ and every $t$ and $t^{\prime}$ such that $t=t^{\prime}$ when $q=q^{\prime}$ , and every $\alpha\in\mathsf{mod}(q)$ and $\alpha^{\prime}\in\mathsf{mod}(q^{\prime})$ , and every compatible histories $h$ and $h^{\prime}$ for $q$ and $q^{\prime}$ , respectively, we have that

\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{\prime}\in% \mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})\right]\leq\frac{tt^{% \prime}}{t^{*}}.

(2)

where $t^{*}=t$ if $(q,\alpha)=(q^{\prime},\alpha^{\prime})$ and $t^{*}=h(\mathsf{lcpn}(\mathsf{path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q^% {\prime}))$ otherwise. In addition if $i$ is even, so $q$ and $q^{\prime}$ are $\lor$ -nodes, then

\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\text{ and }\alpha^{\prime}\in% \hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]\leq\frac{t_{\min}t^{% \prime}_{\min}}{t^{*}}.

(3)

where $t_{\min}=\min(h(c)\mid c\in\mathsf{children}(q))$ and $t^{\prime}_{\min}=\min(h^{\prime}(c)\mid c\in\mathsf{children}(q^{\prime}))$ and $t^{*}=t_{\min}$ if $(q,\alpha)=(q^{\prime},\alpha^{\prime})$ and $t^{*}=h(\mathsf{lcpn}(\mathsf{path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q^% {\prime}))$ otherwise.

The inequalities (2) and (3) are straightforward when $(\alpha,q)=(\alpha^{\prime},q^{\prime})$ because then $h=h^{\prime}$ (by compatibility) and $t=t^{\prime}=t^{*}$ or $t_{\min}=t^{\prime}_{\min}=t^{*}$ and we can use Lemma 9. In particular (2) holds when $q=q^{\prime}=1\text{-sink}$ . Now we assume $(\alpha,q)\neq(\alpha^{\prime},q^{\prime})$ and proceed by induction on $i$ . The base case $i=0$ holds true by the previous remark (note that neither $q$ nor $q^{\prime}$ can be the $0$ -sink because $\mathsf{mod}(q)$ and $\mathsf{mod}(q^{\prime})$ must not be empty).

Case $𝒊$ odd.

In this case $q$ and $q^{\prime}$ are decision nodes. Let $q=ite(x,q_{1},q_{0})$ and $q^{\prime}=ite(y,q^{\prime}_{1},q^{\prime}_{0})$ . Then $h=h_{0}\cup h_{1}\cup\{q_{0}\mapsto t_{0},q_{1}\mapsto t_{1}\}$ for some compatible histories $h_{0}$ and $h_{1}$ for $q_{0}$ and $q_{1}$ , respectively, and $t_{0}$ and $t_{1}$ such that $t=(\frac{1}{t_{0}}+\frac{1}{t_{1}})^{-1}$ . Similarly, $h^{\prime}=h^{\prime}_{0}\cup h^{\prime}_{1}\cup\{q^{\prime}_{0}\mapsto t^{% \prime}_{0},q^{\prime}_{1}\mapsto t^{\prime}_{1}\}$ . Let $b=\alpha(x)$ and $c=\alpha^{\prime}(y)$ . Let also $\beta$ be the restriction of $\alpha$ to $var(\alpha)\setminus\{x\}$ and $\beta^{\prime}$ be the restriction of $\alpha^{\prime}$ to $var(\alpha^{\prime})\setminus\{y\}$ . Then

	$\displaystyle\Pr$	$\displaystyle[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{\prime}\in% \mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})]$
		$\displaystyle=\Pr\left[\beta\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{b},% t_{b}}(q_{b}),\frac{t}{t_{b}}\right),\beta^{\prime}\in\textup{{reduce}}\left(% \mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{c}),\frac{t^{% \prime}}{t^{\prime}_{c}}\right)\right.$
		$\displaystyle\quad\qquad\Big{\|}\,\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})% ,\beta^{\prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_% {c})\bigg{]}\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})\text{ and }% \beta^{\prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{% c})\right]$

Now, because $q$ and $q^{\prime}$ are both in $L_{i}$ , neither is an ancestor of the other and thus the two reduce are independent: the output of one reduce does not modify the set fed into the second reduce nor its output. Thus the probability becomes

	$\displaystyle\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b}),\,\beta^{% \prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{c})% \right]\cdot\Pr\left[\beta\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{b},t_% {b}}(q_{b}),\frac{t}{t_{b}}\right)\Big{\|}\,\beta\in\mathfrak{S}^{r}_{h_{b},t_{% b}}(q_{b})\right]$
	$\displaystyle\cdot\Pr\left[\beta^{\prime}\in\textup{{reduce}}\left(\mathfrak{S% }^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{c}),\frac{t^{\prime}}{t^{% \prime}_{c}}\right)\Big{\|}\,\beta^{\prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},% t^{\prime}_{c}}(q^{\prime}_{c})\right]$

which is equal to $\frac{tt^{\prime}}{t_{b}t^{\prime}_{c}}\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b% },t_{b}}(q_{b})\text{ and }\beta^{\prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t% ^{\prime}_{c}}(q^{\prime}_{c})\right]$ . Now, if $(\beta,q_{b})=(\beta^{\prime},q^{\prime}_{c})$ then $t_{b}=t^{\prime}_{c}$ (because $h$ and $h^{\prime}$ are compatible) and $\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})\text{ and }\beta^{% \prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{c})\right]$ $=\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})\right]=t_{b}=t^{\prime% }_{c}$ by Lemma 9. So $\Pr[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{\prime}\in\mathfrak{% S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})]\leq\frac{tt^{\prime}}{t_{b}}=\frac% {tt^{\prime}}{h(q_{b})}$ . By assumption, $(\alpha,q)\neq(\alpha^{\prime},q^{\prime})$ , if $q\neq q^{\prime}$ then the two derivation paths $\mathsf{path}(\alpha,q)$ and $\mathsf{path}(\alpha^{\prime},q^{\prime})$ diverge for the first time at $q_{b}$ , and if $q=q^{\prime}$ then $x=y$ and $\alpha(x)=1-\alpha^{\prime}(x)$ (because $(\alpha,q)\neq(\alpha^{\prime},q^{\prime})$ by assumption). In this case the derivation paths still diverge for the first time at $q_{b}$ : one follows the $0$ -edge and the other follows the $1$ -edge. So in both cases $\mathsf{lcpn}(\mathsf{path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q^{\prime}% ))=q_{b}$ and we are done. We still have $(\beta,q_{b})\neq(\beta^{\prime},q^{\prime}_{c})$ to consider. In this case the paths $\mathsf{path}(\beta,q_{b})$ and $\mathsf{path}(\beta^{\prime},q^{\prime}_{c})$ diverge for the first time at some node $q^{*}$ below $q_{b}$ and $q^{\prime}_{c}$ so by induction $\Pr\left[\beta\in\mathfrak{S}^{r}_{h_{b},t_{b}}(q_{b})\text{ and }\beta^{% \prime}\in\mathfrak{S}^{r}_{h^{\prime}_{c},t^{\prime}_{c}}(q^{\prime}_{c})% \right]\leq t_{b}t^{\prime}_{c}/h_{b}(q^{*})=t_{b}t^{\prime}_{c}/h(q^{*})$ . So $\Pr[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{\prime}\in\mathfrak{% S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})]\leq tt^{\prime}/h(q^{*})$ . But $q^{*}$ is also the first node where $\mathsf{path}(\alpha,q)$ and $\mathsf{path}(\alpha^{\prime},q^{\prime})$ diverge, hence the result.

Case $𝒊$ even.

In this case $q$ and $q^{\prime}$ are both $\lor$ -nodes. Say $q=q_{1}\lor\dots\lor q_{k}$ and $q^{\prime}=q^{\prime}_{1}\lor\dots\lor q^{\prime}_{m}$ . Then $h=h_{1}\cup\dots\cup h_{k}\cup\{q_{1}\mapsto t_{1},\dots,q_{k}\mapsto t_{k}\}$ and $h^{\prime}=h^{\prime}_{1}\cup\dots\cup h^{\prime}_{k}\cup\{q^{\prime}_{1}% \mapsto t^{\prime}_{1},\dots,q^{\prime}_{m}\mapsto t^{\prime}_{m}\}$ . Let $t_{\min}=\min(t_{1},\dots,t_{k})$ and $t^{\prime}_{\min}=\min(t^{\prime}_{1},\dots,t^{\prime}_{m})$ .

		$\displaystyle\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{% \prime}\in\mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})\right]$
	$\displaystyle=$	$\displaystyle\Pr\left[\alpha\in\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{% h}(q),\frac{t}{t_{\min}}\right)\text{ and }\alpha^{\prime}\in\textup{{reduce}}% \left(\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime}),\frac{t^{\prime}}{t^{% \prime}_{\min}}\right)\right]$
	$\displaystyle=$	$\displaystyle\Pr\left[\alpha\in\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{% h}(q),\frac{t}{t_{\min}}\right),\,\alpha^{\prime}\in\textup{{reduce}}\left(% \hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime}),\frac{t^{\prime}}{t^{\prime}_{% \min}}\right)\Big{\|}\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q),\,\alpha^{\prime}% \in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]$
		$\displaystyle\cdot\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\text{ and }% \alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]$

The reduce events are independent because $q$ and $q^{\prime}$ both belong to $L_{i}$ and thus neither in an ancestor of the other: the output of the first reduce does not influence the output of the second one, even with the knowledge that $\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)$ and $\alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})$ . So the probability becomes

\Pr\left[\alpha\in\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{h}(q),\frac{t% }{t_{\min}}\right)\Big{|}\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\right]\Pr\left% [\alpha^{\prime}\in\textup{{reduce}}\left(\hat{\mathfrak{S}}^{r}_{h^{\prime}}(% q^{\prime}),\frac{t^{\prime}}{t^{\prime}_{\min}}\right)\Big{|}\alpha^{\prime}% \in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]\\ \Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\text{ and }\alpha^{\prime}\in% \hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]

which is $\frac{tt^{\prime}}{t_{\min}t^{\prime}_{\min}}\Pr\left[\alpha\in\hat{\mathfrak{% S}}^{r}_{h}(q),\,\alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{% \prime})\right]$ . Now, there are a unique $j$ and $\ell$ such that $\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)$ only if $\alpha\in\mathfrak{S}^{r}_{h_{j},t_{j}}(q_{j})$ and $\alpha^{\prime}\in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})$ only if $\alpha^{\prime}\in\mathfrak{S}^{r}_{h^{\prime}_{\ell},t^{\prime}_{\ell}}(q^{% \prime}_{\ell})$ . Thus $\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q),\,\alpha^{\prime}\in\hat{% \mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]$ equals

\displaystyle\Pr\left[\alpha\in\textup{{reduce}}\left(\mathfrak{S}^{r}_{h_{j},% t_{j}}(q_{j}),\frac{t_{\min}}{t_{j}}\right),\,\alpha^{\prime}\in\textup{{% reduce}}\left(\mathfrak{S}^{r}_{h^{\prime}_{\ell},t^{\prime}_{\ell}}(q^{\prime% }_{\ell}),\frac{t^{\prime}_{\min}}{t^{\prime}_{\ell}}\right)\right].

$q_{j}$ and $q^{\prime}_{\ell}$ belong to the same layer so with similar arguments we find that

\displaystyle\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\text{ and }\alpha% ^{\prime}\in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]=\frac{t_{% \min}t^{\prime}_{\min}}{t_{j}t^{\prime}_{l}}\Pr\left[\alpha\in\mathfrak{S}^{r}% _{h_{j},t_{j}}(q_{j})\text{ and }\alpha^{\prime}\in\mathfrak{S}^{r}_{h^{\prime% }_{\ell},t^{\prime}_{\ell}}(q^{\prime}_{\ell})\right].

It is possible that $(\alpha,q_{j})=(\alpha^{\prime},q^{\prime}_{\ell})$ but then $q\neq q^{\prime}$ for otherwise we would have $(\alpha,q)=(\alpha^{\prime},q^{\prime})$ , against assumption. In the case $(\alpha,q_{j})=(\alpha^{\prime},q^{\prime}_{\ell})$ we use Lemma 9 and find $\Pr\left[\alpha\in\mathfrak{S}^{r}_{h_{j},t_{j}}(q_{j})\text{ and }\alpha^{% \prime}\in\mathfrak{S}^{r}_{h^{\prime}_{\ell},t^{\prime}_{\ell}}(q^{\prime}_{% \ell})\right]=\Pr\left[\alpha\in\mathfrak{S}^{r}_{h_{j},t_{j}}(q_{j})\right]=t% _{j}=t^{\prime}_{\ell}$ . So

\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q)\text{ and }\alpha^{\prime}\in% \hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]=\frac{t_{\min}t^{\prime% }_{\min}}{t_{j}}

and $\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(q)\text{ and }\alpha^{\prime}\in% \mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})\right]=\frac{tt^{\prime}}% {t_{j}}$ . When $(\alpha,q_{j})=(\alpha^{\prime},q^{\prime}_{\ell})$ , the paths $\mathsf{path}(\alpha,q)$ and $\mathsf{path}(\alpha^{\prime},q^{\prime})$ diverge for the first time at $q_{j}=q^{\prime}_{\ell}$ . So $t_{j}=h(\mathsf{lcpn}(\mathsf{path}(\alpha,q),\mathsf{path}(\alpha^{\prime},q^% {\prime})))$ and we are done. Now let us assume that $(\alpha,q_{j})\neq(\alpha^{\prime},q^{\prime}_{\ell})$ , then we use the induction hypothesis and, denoting $q^{*}=\mathsf{lcpn}(\mathsf{path}(\alpha,q_{j}),\mathsf{path}(\alpha^{\prime},% q^{\prime}_{\ell}))$ , we have

\displaystyle\Pr\left[\alpha\in\hat{\mathfrak{S}}^{r}_{h}(q),\,\alpha^{\prime}% \in\hat{\mathfrak{S}}^{r}_{h^{\prime}}(q^{\prime})\right]\leq\frac{t_{\min}t^{% \prime}_{\min}}{h(q^{*})}\text{ and }\Pr\left[\alpha\in\mathfrak{S}^{r}_{h,t}(% q),\,\alpha^{\prime}\in\mathfrak{S}^{r}_{h^{\prime},t^{\prime}}(q^{\prime})% \right]\leq\frac{tt^{\prime}}{h(q^{*})}

When $(\alpha,q_{j})\neq(\alpha^{\prime},q^{\prime}_{\ell})$ , the first node where $\mathsf{path}(\alpha,q)$ and $\mathsf{path}(\alpha^{\prime},q^{\prime})$ diverge is also the first node where $\mathsf{path}(\alpha,q_{j})$ and $\mathsf{path}(\alpha^{\prime},q^{\prime}_{\ell})$ diverge, so $q^{*}$ . This finishes the proof of the inductive case. $\hfill\blacktriangleleft$

[bib.bib1] [1] Antoine Amarilli, Marcelo Arenas, YooJung Choi, Mikaël Monet, Guy Van den Broeck, and Benjie Wang. A circus of circuits: Connections between decision diagrams, circuits, and automata. arXiv preprint arXiv:2404.09674, 2024. doi:10.48550/arXiv.2404.09674.

[bib.bib2] [2] Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. SIGMOD Rec., 53(2):6–20, 2024. doi:10.1145/3685980.3685982.

[bib.bib3] [3] Antoine Amarilli and Florent Capelli. Tractable circuits in database theory. ACM SIGMOD Record, 53(2):6–20, 2024. doi:10.1145/3685980.3685982.

[bib.bib4] [4] Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory Comput. Syst., 64(5):861–914, 2020. doi:10.1007/S00224-019-09930-2.

[bib.bib5] [5] Antoine Amarilli, Timothy van Bremen, and Kuldeep S Meel. Conjunctive queries on probabilistic graphs: The limits of approximability. In 27th International Conference on Database Theory, 2024.

[bib.bib6] [6] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. Efficient logspace classes for enumeration, counting, and uniform generation. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, pages 59–73. ACM, 2019. doi:10.1145/3294052.3319704.

[bib.bib7] [7] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. When is approximate counting for conjunctive queries tractable? In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1015–1027. ACM, 2021. doi:10.1145/3406325.3451014.

[bib.bib8] [8] Paul Beame and Vincent Liew. New limits for knowledge compilation and applications to exact model counting. arXiv preprint arXiv:1506.02639, 2015. arXiv:1506.02639.

[bib.bib9] [9] Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Trans. Computers, 35(8):677–691, 1986. doi:10.1109/TC.1986.1676819.

[bib.bib10] [10] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. J. Artif. Intell. Res., 17:229–264, 2002. doi:10.1613/JAIR.989.

[bib.bib11] [11] Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet. Computing the shapley value of facts in query answering. In SIGMOD ’22: International Conference on Management of Data, pages 1570–1583. ACM, 2022. doi:10.1145/3514221.3517912.

[bib.bib12] [12] Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Inf. Comput., 134(1):59–74, 1997. doi:10.1006/INCO.1997.2621.

[bib.bib13] [13] Abhay Kumar Jha and Dan Suciu. On the tractability of query compilation and bounded treewidth. In 15th International Conference on Database Theory, ICDT ’12, pages 249–261. ACM, 2012. doi:10.1145/2274576.2274603.

[bib.bib14] [14] Abhay Kumar Jha and Dan Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst., 52(3):403–440, 2013. doi:10.1007/S00224-012-9392-5.

[bib.bib15] [15] Sheldon B. Akers Jr. Binary decision diagrams. IEEE Trans. Computers, 27(6):509–516, 1978. doi:10.1109/TC.1978.1675141.

[bib.bib16] [16] Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. Counting and random generation of strings in regular languages. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 551–557. ACM/SIAM, 1995. URL: http://dl.acm.org/citation.cfm?id=313651.313803.

[bib.bib17] [17] Richard M. Karp and Michael Luby. Monte-carlo algorithms for enumeration and reliability problems. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 56–64. IEEE Computer Society, 1983. doi:10.1109/SFCS.1983.35.

[bib.bib18] [18] Kuldeep S. Meel, Sourav Chakraborty, and Umang Mathur. A faster FPRAS for #nfa. Proc. ACM Manag. Data, 2(2):112, 2024. doi:10.1145/3651613.

[bib.bib19] [19] Stefan Mengel. Counting, Knowledge Compilation and Applications. PhD thesis, Université d’Artois, 2021.

[bib.bib20] [20] Mikaël Monet. Solving a special case of the intensional vs extensional conjecture in probabilistic databases. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, pages 149–163. ACM, 2020. doi:10.1145/3375395.3387642.

[bib.bib21] [21] Mikaël Monet and Dan Olteanu. Towards deterministic decomposable circuits for safe queries. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 2100 of CEUR Workshop Proceedings. CEUR-WS.org, 2018. URL: https://ceur-ws.org/Vol-2100/paper19.pdf.

[bib.bib22] [22] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410–421, 1979. doi:10.1137/0208032.

[bib.bib23] [23] Ingo Wegener. Branching Programs and Binary Decision Diagrams. SIAM, 2000. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bdd/.

	$\displaystyle\Pr_{\texttt{A}}$	$\displaystyle\left[\mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(1)\|\right]$
		$\displaystyle=\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\bigcap_{r,q}\|S^{r}(q)\|<\theta\text{ and }% \mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(1)\|\right]$
		$\displaystyle\leq\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\mathsf{est}\not\in(1\pm\varepsilon)\|B^{-1}(% 1)\|\right]$
		$\displaystyle\leq\Pr_{\texttt{A}^{}}\left[\bigcup_{r,q}\|S^{r}(q)\|\geq\theta% \right]+\Pr_{\texttt{A}^{}}\left[\bigcup_{q}p(q)\not\in\frac{1}{(1\pm% \varepsilon)\|\mathsf{mod}(q)\|}\right]$

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

#nFBDD.

Theorem 1.

Organization of the paper.

2 Background

nBDD.

nFBDD.

Lemma 2.

Proof sketch.

FPRAS.

2.1 Related Work

3 Technical Overview

4 Algorithm

5 Derivation paths

Definition 3.

Lemma 4.

Proof.

Definition 5.

Lemma 6.

Proof.

6 The Framework for the Analysis

6.1 History

6.2 Random Process

Fact 7.

Fact 8.

Lemma 9.

Lemma 10.

7 Analysis

Lemma 11.

Proof.

Lemma 12.

Lemma 13.

Proof of Lemma 11.

7.1 Proof of Lemma 12

Claim 14.

Proof.

Going to the random process

Claim 15.

Proof.

Variance upper bound

Median of means

7.2 Proof of Lemma 13

8 Conclusion

References

Appendix A Appendix

Proof.

Proof.

Case 𝒊 odd.

Case 𝒊 even.

Case $𝒊$ odd.

Case $𝒊$ even.