Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions
Banghua Zhu Ziao Wang Nadim Ghaddar Jiantao Jiao Lele Wang
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
\in (0,1/2)$. Specifically, we consider the computation of the $\mathsf{OR}$
function of $n$ bits (where queries correspond to noisy readings of the bits)
and the $\mathsf{MAX}$ function of $n$ real numbers (where queries correspond
to noisy pairwise comparisons). We show that an expected number of queries of
\[ (1 \pm o(1)) \frac{n\log \frac{1}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)} \] is
both sufficient and necessary to compute both functions with a vanishing error
probability $\delta = o(1)$, where $D_{\mathsf{KL}}(p \| 1-p)$ denotes the
Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(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.