On the Optimal Bounds for Noisy Computing
On the Optimal Bounds for Noisy Computing
We revisit the problem of computing with noisy information considered in Feige et al. [1], which includes computing the OR function from noisy queries, and computing the MAX, SEARCH, and SORT functions from noisy pairwise comparisons. For K given elements, the goal is to correctly recover the desired function with …