无界错误通信复杂度

形式陈述

取有限非空 $X,Y$ 。对 $f:X\times Y\to\{\pm1\}$ ，记符号矩阵为 $S_f=(f(x,y))$ 。无界错误协议采用私有币口径，双方随机带彼此独立；对每个输入都要求

\Pr[\Pi(x,y)=f(x,y)]>\frac12.

优势 $\beta_{xy}=\Pr[\text{correct}]-1/2$ 可依赖输入，规格不预先要求统一的正下界。 $\operatorname{UPP}^{\mathrm{cc}}(f)$ 是满足该严格条件的协议的最坏通信 bit 数下确界；有限输入集上可取到一个正的最小优势，但复杂度定义不向它收费。本页先规定 Bob 输出，并采用由公开消息前缀决定发言者与终止的私有币协议。若要求双方输出，Bob 最后再发送一 bit；以下刻画把这项固定开销吸收到 $O(1)$ 。

关键刻画是

\operatorname{UPP}^{\mathrm{cc}}(f) =\log_2\operatorname{signrank}(S_f)+O(1).

从成本 $c$ 的私有币协议到矩阵：令 $A_{xy}=\Pr[\Pi=1]-\Pr[\Pi=-1]$ 。严格成功保证 $S_{xy}A_{xy}>0$ 。合法私有币协议的因子分解还说明，Bob 给定自身输入和 transcript 后的私有带后验不依赖 Alice 输入。于是每条 transcript 对中心化输出期望的贡献可写成 $a_t(x)b_t(y)$ ，其中 $b_t$ 可带正负号；至多 $2^c$ 条 transcript 相加给出 $\operatorname{rank}(A)\le2^c$ 。

反向可直接构造一条单向协议。设严格同号矩阵 $A=UV^{\mathsf T}$ 的秩为 $r\ge1$ ，记行向量为 $u_x,v_y$ ，令

L_x=\sum_{i=1}^r|u_{x,i}|>0, \qquad M_y=\max_{1\le i\le r}|v_{y,i}|>0.

Alice 以概率 $|u_{x,i}|/L_x$ 选择坐标 $i$ ，发送其固定长编号和 $u_{x,i}$ 的符号。Bob 输出一个 $\{\pm1\}$ 随机值，使其条件期望为 $\operatorname{sign}(u_{x,i})v_{y,i}/M_y$ ；此数在 $[-1,1]$ 内，因此可用输出 $+1$ 的概率 $(1+\operatorname{sign}(u_{x,i})v_{y,i}/M_y)/2$ 实现。零坐标不会被 Alice 抽到。平均后，输出期望为

\frac{\langle u_x,v_y\rangle}{L_xM_y},

与目标符号严格相同，所以每个输入都以严格大于 $1/2$ 的概率正确。通信仅为 $\lceil\log_2r\rceil+1$ bit；本地抽样计算不收费。这个构造与前向分解一起给出所述对数刻画，也说明任意交互 UPP 协议可在常数附加通信内化为单向协议。

直觉

bounded-error 模型关心离 $1/2$ 有固定距离；UPP 只关心越过哪一侧。因此一个协议可以用极其微弱的偏置编码答案，只要每个输入都严格为正。中心化的接受概率矩阵恰好把“微弱但正确”变成一张无零的符号实现矩阵。

模型的力量来自不为优势付费。若某输入优势为 $2^{-2^n}$ ，把它放大到 $1/6$ 需要天文数量的独立重复；UPP 仍把原协议看作成功。这解释了符号秩为何刻画 UPP，却不能直接刻画普通 randomized complexity。

例子与边界

任意有限函数都展示公共币禁区。公共币均匀抽取 $(x',y')\in X\times Y$ ；Alice 发送 $a=\mathbf1[x=x']$ 。Bob 检查 $b=\mathbf1[y=y']$ ：若 $a=b=1$ ，输出公开可算的 $f(x',y')$ ；否则抛公平私有币。对真实输入 $(x,y)$ ，命中事件概率为 $1/(|X||Y|)$ ，故

\Pr[\text{correct}]=\frac12+\frac1{2|X||Y|}>\frac12.

协议只发一 bit（若要求双方输出，再回传一 bit），于是 public-coin UPP 会把所有有限函数压到常数复杂度。标准 Paturi–Simon 刻画必须采用私有币，不能把 public coin 当作无害加强。

对一 bit XOR，符号秩页给出秩一矩阵

S=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}=uv^{\mathsf T}.

Alice 甚至可发送自己的输入一 bit，Bob 确定输出，故 UPP 成本为常数； $\log_2\operatorname{signrank}(S)=0$ ，差异正落在输出 convention 的加性常数内。这个例子也说明为何不能宣称二者字面相等。

若把严格 $>1/2$ 改为 $\ge1/2$ ，永远抛公平硬币的零通信协议对所有函数都合法，模型完全坍塌。若要求统一优势至少 $1/6$ ，则回到 bounded-error randomized 模型。若允许公共币，必须另行固定随机性资源与有限精度，不能继续引用上述等价式。

推论与应用

UPP 下界等价于证明所有低秩实矩阵都无法严格实现目标符号模式；协议轮数在刻画中消失，因为任意两向 UPP 协议都能常数开销化为一向几何协议。它因此适合把通信问题转成点—超平面排列、阈值电路和学习维数问题。

等价刻画保留的是对数数量关系与加性常数，不保留偏置、round 或每条消息长度。同一私有币模型下，固定错误协议是 UPP 协议的子类，故 $R^{\mathrm{priv}}_\varepsilon(f)\ge\operatorname{UPP}^{\mathrm{cc}}(f)$ （ $\varepsilon<1/2$ ），UPP 下界可以直接传递。小 UPP 上界则不能忽略优势大小而免费变成 bounded-error 上界。若改用公币或需要更强的定量、轮数结论，应另用近似秩、分解范数、信息复杂度等工具。

参考资料

Ramamohan Paturi and Janos Simon, “Probabilistic Communication Complexity,” Journal of Computer and System Sciences 33(1), 1986, pp. 106–123.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 3.
Alexander A. Sherstov, “The Unbounded-Error Communication Complexity of Symmetric Functions,” Combinatorica 31, 2011, pp. 583–614.

形式陈述 ​

反向链接

形式陈述