Noisy Computing of the mathsfOR and mathsfMAX Functions

We consider the problem of computing a function of n variables using noisy queries, where each query is incorrect with some fixed and known probability p ∈ (0,1/2). Specifically, we consider the computation of the mathsfOR function of n bits (where queries correspond to noisy readings of the bits) and the mathsfMAX function of n real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of [ (1 ± o(1)) fracnlog frac1δD_mathsfKL(p | 1-p) ] is both sufficient and necessary to compute both functions with a vanishing error probability δ = o(1), where D_mathsfKL(p | 1-p) denotes the Kullback-Leibler divergence between mathsfBern(p) and mathsfBern(1-p) distributions. Compared to previous work, our results tighten the dependence on p in both the upper and lower bounds for the two functions.