# Noisy Computing of the mathsfOR and mathsfMAX Functions

arXiv: https://arxiv.org/abs/2309.03986 · HTML: https://mlsanity.com/paper/2309.03986/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 51 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 10 of 10)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Generalized Resilience and Robust Statistics](https://mlsanity.com/paper/1909.08755/) (2019)
- [Machine Learning for Reliability Engineering and Safety Applications: Review of Current Status and Future Opportunities](https://mlsanity.com/paper/2008.08221/) (2020)
- [Maximum Selection and Ranking under Noisy Comparisons](https://mlsanity.com/paper/1705.05366/) (2017)
- [Optimal Bounds for Noisy Sorting](https://mlsanity.com/paper/2302.12440/) (2023)
- [When does the Tukey median work?](https://mlsanity.com/paper/2001.07805/) (2020)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)

## Built on by (most cited first, 1 of 1)

- [Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits](https://mlsanity.com/paper/2503.00273/) (2025)

## Abstract (arXiv)

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.