Communication with Contextual Uncertainty
Communication with Contextual Uncertainty
复制标题
与情境不确定性进行沟通
DOI：
10.1007/s00037-017-0161-3
复制
发表时间：
2018
影响因子：
1.4
通讯作者：
Sudan, Madhu
中科院分区：
文献类型：
--
作者：
Ghazi, Badih;Komargodski, Ilan;Kothari, Pravesh K.;Sudan, Madhu
我们介绍了一个简单的模型，说明在压缩通信和上下文知识的不确定性所带来的挑战的实用程序。我们考虑分布式通信复杂度的一个变体，其中Alice得到一些信息，Bob得到，其中（X，Y）是从已知分布中得出的，Bob希望计算一些函数g（X，Y）或它的一些近似值（即，输出是g（X，Y），具有超过（X，Y）的高概率）。在我们的变体中，爱丽丝不知道g，但只知道某个函数f，它非常接近g。因此，正在计算的函数形成了通信的上下文。这是一个巨大的隐式输入，可能由大小为2n的真值表描述。不精确的知识，这个功能模型（轻度）的不确定性在这种情况下，我们表明，不确定性会导致巨大的成本在沟通。具体地说，我们构造了一个分布在和一类函数对（f，g），它们非常接近（即，不同意o（1）概率时（X，Y）被采样根据），其中形成的通信复杂度在标准设置是一个比特，而（双向）通信复杂度在不确定设置是至少比特，即使允许一个恒定的错误概率.事实证明，这种爆炸的通信复杂度可以部分归因于X和Y之间的互信息.特别是，我们给出了一个有效的协议，在上下文不确定性的情况下，只会引起一个小的爆炸，如果这个相互信息是小的通信。也就是说，如果在标准设置和X与Y之间的互信息下有一个复杂性的通信协议，那么在不确定设置下有一个复杂性的单向通信协议。这个结果是一个更强结果的直接推论，该结果表明，如果h具有单向通信复杂度k，则它至多具有单向不确定通信复杂度。在输入分布为乘积分布（且soI= 0）的特殊情况下，不确定环境下的协议只会在单向通信中引起常数因子爆破和错误.
We introduce a simple model illustrating the utility of context in compressing communication and the challenge posed by uncertainty of knowledge of context. We consider a variant ofdistributionalcommunication complexity where Alice gets some informationand Bob gets, where (X,Y) is drawn from a known distribution, and Bob wishes to compute some functiong(X,Y) or some close approximation to it (i.e., the output isg(X,Y) with high probability over (X,Y)). In our variant, Alice does not knowg, but only knows some functionfwhich is a very close approximation tog. Thus, the function being computed forms the context for the communication. It is an enormous implicit input, potentially described by a truth table of size 2n. Imprecise knowledge of this function models the (mild) uncertainty in this context.We show that uncertainty can lead to a huge cost in communication. Specifically, we construct a distributionoverand a class of function pairs (f,g) which are very close (i.e., disagree witho(1) probability when (X,Y) are sampled according to), for which the communication complexity offorgin the standard setting isone bit, whereas the (two-way) communication complexity in the uncertain setting is at leastbits even when allowing a constant probability of error.It turns out that this blow-up in communication complexity can be attributed in part to the mutual information betweenXandY. In particular, we give an efficient protocol for communication under contextual uncertainty that incurs only a small blow-up in communication if this mutual information is small. Namely, we show that ifghas a communication protocol with complexitykin the standard setting and the mutual information betweenXandYisI, thenghas a one-way communication protocol with complexityin the uncertain setting. This result is an immediate corollary of an even stronger result which shows that ifghas one-way communication complexityk, then it has one-way uncertain-communication complexity at most. In the particular case where the input distribution is a product distribution (and soI= 0), the protocol in the uncertain setting only incurs aconstant factorblow-up in one-way communication and error.
登录
查看更多内容
DOI：
10.1145/2160158.2160161
发表时间：
2012-04
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Oded Goldreich;Brendan Juba;M. Sudan
通讯作者：
Oded Goldreich;Brendan Juba;M. Sudan
影响因子：
0.5
作者：
Huang, Wei;Shi, Yaoyun;Zhu, Yufan
通讯作者：
Zhu, Yufan
论共享随机性在同步通信中的作用
DOI：
10.1007/978-3-662-43948-7_13
发表时间：
2014
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Mohammad Bavarian;Dmitry Gavinsky;Tsuyoshi Ito
通讯作者：
Tsuyoshi Ito
具有不确定先验的确定性压缩
影响因子：
1.1
作者：
Elad Haramaty;M. Sudan
通讯作者：
M. Sudan
关于从相关源中提取公共随机位
影响因子：
2.5
作者：
Andrej Bogdanov;Elchanan Mossel
通讯作者：
Elchanan Mossel