Round Complexity of Common Randomness Generation: The Amortized Setting
Round Complexity of Common Randomness Generation: The Amortized Setting
复制标题
常见随机性生成的轮复杂度：摊销设置
DOI：
10.1137/1.9781611975994.66
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sudan, Madhu
中科院分区：
文献类型：
--
作者：
Golowich, Noah;Sudan, Madhu
在这项工作中，我们研究了影响轮的相互作用的共同随机生成（CRG）的问题。在CRG问题中，Alice和Bob两方分别接收样本XiandYi，其中（Xi，Yi）是从一个随机分布μ中共同抽取的。双方希望通过交换依赖于各自输入和先前消息的消息，就由许多随机比特组成的公共随机密钥达成一致。在这项工作中，我们研究的问题，即，Alice和Bob输出的每个随机比特所需的通信比特数，在所生成的比特数趋于无穷大的极限中。CRG问题的摊销版本在信息论文献中得到了广泛的研究，尽管人们对交互作用对该问题的影响知之甚少。最近Bafna et al.（SODA 2019）考虑了该问题的非摊销版本（因此，这里交互的目标是生成固定数量的随机位）：他们给出了一个由r，n参数化的源族μr，n，使得在r + 2轮通信的情况下，可以在O（rlogn）通信的情况下用这个源生成10位公共随机性，而对于粗略的r/2轮，通信复杂度是n/polylogn。特别要注意的是，他们的源设计的目标位数，因此结果不适用于摊销setting.In这项工作中，我们加强了巴夫纳等人的工作。在两个方面：首先，我们表明，结果扩展到经典的摊销设置。我们还减少了差距轮复杂度的上限和下限之间的一个附加常数。具体地说，我们证明了对于每对r，n，从源μr，nusingr+ 2轮通信生成<$（n）位公共随机性的（摊销）通信复杂度是O（rlogn），而从r轮生成相同数量的随机性所需的摊销通信是。我们的技术利用了信息复杂度和CRG之间的已知联系，主要的新奇是我们能够分析从源μr，n获得输入的协议的信息复杂度。
In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samplesXiandYi, respectively, where (Xi, Yi) are drawn jointly from asource distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study theamortizedversion of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered thenon-amortizedversion of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sourcesμr,nparameterized byr,nϵ ℕ, such that withr+ 2 rounds of communication one can generatenbits of common randomness with this source withO(rlogn) communication, whereas with roughlyr/2 rounds the communication complexity isΩ(n/poly logn). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting.In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pairr, nϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the sourceμr,nusingr+ 2 rounds of communication isO(rlogn) whereas the amortized communication required to generate the same amount of randomness fromrrounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the sourceμr,n.
登录
查看更多内容
最坏情况交互通信一：两条消息几乎是最优的
影响因子：
2.5
作者：
A. Orlitsky
通讯作者：
A. Orlitsky
DOI：
--
发表时间：
2019
期刊：
Innovations in Theoretical Computer Science Conference
影响因子：
--
作者：
Haitner, Iftach;Mazor, Noam;Oshman, Rotem;Reingold, Omer;Yehudayoff, Amir
通讯作者：
Yehudayoff, Amir
使用一个通信器生成密钥并通过超收缩性进行一次性对话
DOI：
10.1109/isit.2015.7282697
发表时间：
2015
期刊：
2015 IEEE International Symposium on Information Theory (ISIT)
影响因子：
--
作者：
Jingbo Liu;P. Cuff;S. Verdú
通讯作者：
S. Verdú
影响因子：
1
作者：
J. A. Fill;Nevin Kapur
通讯作者：
Nevin Kapur
论共享随机性在同步通信中的作用
DOI：
10.1007/978-3-662-43948-7_13
发表时间：
2014
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Mohammad Bavarian;Dmitry Gavinsky;Tsuyoshi Ito
通讯作者：
Tsuyoshi Ito