计算“或”和“最大值”函数的噪声方法

Sep, 2023

计算“或”和“最大值”函数的噪声方法

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

Banghua Zhu, Ziao Wang, Nadim Ghaddar, Jiantao Jiao, Lele Wang

TL;DR使用有噪声的查询计算具有错误概率的函数问题，给出了计算OR函数和MAX函数所需的期望查询次数，并在两个函数的上下界中对错误概率进行了更紧密的依赖。

Abstract

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)$. Specifically, we consider the computation