Noisy Computing of the $\mathsf{O}\mathsf{R}$ and $\mathsf{M}\mathsf{A}\mathsf{X}$ 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\in (0,1\mathrm{/}2)$. Specifically, we consider the computation of the $\mathsf{O}\mathsf{R}$ function of $n$ bits (where queries correspond to noisy readings of the bits) and the $\mathsf{M}\mathsf{A}\mathsf{X}$ 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{K}\mathsf{L}}(p\mathrm{\parallel }1-p)}$$ is both sufficient and necessary to compute both functions with a vanishing error probability $\delta =o(1)$, where $D_{\mathsf{K}\mathsf{L}}(p\mathrm{\parallel }1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{B}\mathsf{e}\mathsf{r}\mathsf{n}(p)$ and $\mathsf{B}\mathsf{e}\mathsf{r}\mathsf{n}(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.