Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions

Banghua Zhu, Ziao Wang, Nadim Ghaddar +2

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)$. Specifica…