Noisy Computing of the Threshold Function

Let mathsfTHk 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 mathsfTHk 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 it is sufficient to use (1+o(1)) fracnlog fracmδD_mathsfKL(p | 1-p) queries in expectation to compute the mathsfTHk function with a vanishing error probability δ = o(1), where mtriangleq mink,n-k+1 and D_mathsfKL(p | 1-p) denotes the Kullback-Leibler divergence between mathsfBern(p) and mathsfBern(1-p) distributions. Conversely, we show that any algorithm achieving an error probability of δ = o(1) necessitates at least (1-o(1))frac(n-m)logfracmδD_mathsfKL(p | 1-p) queries in expectation. The upper and lower bounds are tight when m=o(n), and are within a multiplicative factor of fracnn-m when m=Theta(n). In particular, when k=n/2, the mathsfTHk function corresponds to the mathsfMAJORITY function, in which case the upper and lower bounds are tight up to a multiplicative factor of two. Compared to previous work, our result tightens the dependence on p in both the upper and lower bounds.