Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold

Yuzhou Gu, Xin Li, Yinzhan Xu

In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability $p\in (0,1/2)$. In this paper, we obta…