Noisy Computing of the Threshold Function

Let THₖ denote the k-out-of-n threshold function: given n input Boolean variables, the output is $1$ if and only if at least k of the inputs are $1$. We consider the problem of computing the THₖ function using noisy readings of the Boolean variables, where each reading is incorrect with some fixed and known probability p ∈ (0,1/2). As our main result, we show that, when $k = o(n)$, it is both sufficient and necessary to use (1 ± o(1)) nlog k/δDKL(p || 1-p) queries in expectation to compute the THₖ function with a vanishing error probability δ = o(1), where DKL(p || 1-p) denotes the Kullback-Leibler divergence between Bern(p) and Bern(1-p) distributions. In particular, this says that (1 ± o(1)) nlog 1/δDKL(p || 1-p) queries in expectation are both sufficient and necessary to compute the OR and AND functions of n Boolean variables. Compared to previous work, our result tightens the dependence on p in both the upper and lower bounds.