  We study the witness-counting problem: given a set of vectors $V$ in the
$d$-dimensional vector space over $\mathbb{F}_2$, a target vector $t$, and an
integer $k$, count all ways to sum-up exactly $k$ different vectors from $V$ to
reach $t$. The problem is well-known in coding theory and received considerable
attention in complexity theory. Recently, it appeared in the context of
hardware monitoring.
  Our contribution is an algorithm for witness counting that is optimal in the
sense of fine-grained complexity. It runs in time $\mathcal{O}^*(2^d)$ with
only a logarithmic dependence on $m=|V|$. The algorithm makes use of the
Walsh-Hadamard transform to compute convolutions over $\mathbb{F}_2^d$. The
transform, however, overcounts the solutions. Inspired by the
inclusion-exclusion principle, we introduce correction terms. The correction
leads to a recurrence that we show how to solve efficiently. The correction
terms are obtained from equivalence relations over $\mathbb{F}_2^d$.
  We complement our upper bound with two lower bounds on the problem. The first
relies on $\# ETH$ and prohibits an $2^{o(d)}$-time algorithm. The second bound
states the non-existence of a polynomial kernel for the decision version of the
problem.
