通信复杂度

2016-10-15

通信复杂度的问题最初由姚期智(现任清华叉院院长,膜)提出,主要是用于量化在分布式计算中所需的通信量的多少。对于两个在不同位置的人,Alice和Bob,Alice收到一个n比特的字符串x,Bob收到另外一个n比特的字符串y,那么我们的目标是让他们用最小的通信量来计算一个函数\(f(x,y)\),但我们并不关心具体需要多少步才能完成计算,也不关心需要多少内存,重点是优化通信所占用的资源。

定义

一个 t-round 的通信协议是一个函数对的序列

\[ (S_1,C_1),(S_2,C_2),\dots,(S_t,C_t),(f_1,f_2) \]

\(S_i\)的输入是