Time complexity of a problem in probabilistic inference on a Bayesian network

Question

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

We would like to find the probability of the joint event $E$ that both (i) all $y_k$ are 1 and (ii) the total assignment of states on the network has a probability above $\epsilon$.

Is exponential time required to compute the probability of $E$, and if so (or not), how do we prove this?

---

In case it is helpful, let me give a low-$n$ example:

Suppose $n = 3$. If we just want to compute the probability of (i), then this is $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0}p_{2,0}p_{3,0} + p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,0} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,0}p_{3,1} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$ We can factor the right-hand side so that rather than a sum of $2^3$ terms we just have a product of $3$ factors: $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0} + p_{1,1})(p_{2,0} + p_{2,1})(p_{3,0} + p_{3,1}).$$ This reduces our computational time from $O(2^n)$ to $O(n)$ (as shown here for arbitrary $n$).

However, now consider the case that the terms $p_{1,0}p_{2,0}p_{3,0}$, $p_{1,0}p_{2,1}p_{3,0}$, and $p_{1,1}p_{2,0}p_{3,1}$ are quite small -- each less than $\epsilon$ -- and we would like our overall probability to 'ignore' such small terms. Then we want to compute: $$\Pr(E) = 2^{-3}(p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$

Of course, no generalizable factorization seems possible for the right-hand side. This motivates the above question: how can we prove (or disprove) that computing $\Pr(E)$ in the case of arbitrary $n$, $p_{k,0}$, $p_{k,1}$, and $\epsilon$ is indeed $\Omega(2^n)$?