# Hardness of exact binomial tail bounds

Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. Suppose that $p$ and $t$ are specified with $O(n)$ bits -- this precision level is sufficient to describe all of the outputs in the range of $F$. I strongly suspect that there is no poly(n) time algorithm for computing $F$ exactly; is there any formal evidence of this?

Edit. As pointed out in the comments, the function above is of course computable in polynomial time. How about the following variant: $X_i$ are independent symmetric Bernoulli variables and $w_i\in[0,1]$ are weights specified with $O(n)$ bits each. Define the function $$F(w,t):=P( \sum_{i=1}^n w_i X_i > t) .$$ Hoeffding's inequality provides exponential bounds on $F$; what is the complexity of computing $F$ exactly?

• I'm pretty sure there is a poly(n)-time algorithm for the problem you describe using the binomial expansion. – Thomas Sep 17 '17 at 18:34
• You want to compute $\sum_{k=\lfloor t+1 \rfloor}^n {n \choose k} p^k (1-p)^{n-k}$ and I don't see why that can't be done in poly time. – Thomas Sep 17 '17 at 18:38
• You're right, of course! I was going for the simplest non-trivial variant but hit a trivial one :) – Aryeh Sep 17 '17 at 20:13
• My gut feeling is that the second variant is #P-hard. You're counting the number of solutions $x \in \{0,1\}^n$ to the equation $\sum_i^n w_ix_i >t$, which seems vaguely like a counting version of the knapsack problem. – Thomas Sep 17 '17 at 22:00
• I think that for approximate counting it is still in P because via rapid mixing results by Morris (if I remember correctly). – Gil Kalai Sep 19 '17 at 19:47

Theorem Exactly computing $F(w,t)$ is #P-hard.
proof. Reduce from the counting version of Subset Sum, the #Subset Sum problem, defined as follows. Input is a set $W = w_1, \ldots, w_n$ of non-negative integers, and an integer $t$. The task is to count the number of subsets $W' \subseteq W$ that add up to exactly $t$. This problem is known to be #P-hard, even when for all $i$, $w_i \leq t$ and $t = 2^{O(n)}$. In particular, the $w_i$'s are $O(n)$ bit integers.
$$2^n \cdot \left( F(\frac{W}{t}, 1-\frac{1}{t}) - F(\frac{W}{t}, 1) \right) = 2^n \cdot P\left[\sum_{i=1}^n \frac{w_iX_i}{t} = 1 \right],$$ which is precisely the number of subsets of $W$ that add up to $t$.