Reliable communication over highly connected noisy networks
Reliable communication over highly connected noisy networks
复制标题
通过高度连接的嘈杂网络进行可靠通信
DOI：
10.1007/s00446-017-0303-5
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
Haeupler, Bernhard
中科院分区：
文献类型：
--
作者：
Alon, Noga;Braverman, Mark;Efremenko, Klim;Gelles, Ran;Haeupler, Bernhard
我们考虑在随机噪声存在下，在网络上进行多方计算的任务。给定假设无噪声通信进行循环的一方协议，目标是找到一种编码方案，即使在通信有噪声时，该编码方案也进行R '循环并以高概率计算相同的函数，同时保持恒定的渐近速率，即，Rajagopalan和Schulman（STOC '94）首先考虑了这一问题，并提出了一种码率为O（1/log（d+1））的编码方案，其中R是网络的最大度。虽然该方案为许多实际情况提供了恒定速率编码，但在最坏的情况下，当网络是完全图时，编码率为~O（1/logn），趋于0，趋于无穷大.我们重新讨论了这个问题，并为全连通网络的有趣情况提供了一个具有恒定编码率的有效编码方案.我们进一步推广了这个结果，证明了如果一个d-正则网络的混合时间为m，则存在一个码率为O（1/m3 logm）的有效编码方案.这意味着在具有常数混合时间的ad-正则网络上的任意方协议中，特别是对于顶点和度为n Ω（1）的随机图，可以采用常数速率编码方案。
We consider the task of multiparty computation performed over networks in the presence of random noise. Given ann-party protocol that takesrounds assuming noiseless communication, the goal is to find a coding scheme that takesR'rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptoticrate, i.e., while keepingn,R→∞R/R'positive.Rajagopalan and Schulman (STOC '94) were the first to consider this question, and provided a coding scheme with rateO(1/log (d+1)), wheredis the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is~O(1/logn), which tends to0asntends to infinity.We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a (d-regular) network has mixing timem, then there exists an efficient coding scheme with rateO(1/m3logm). This implies a constant rate coding scheme for anyn-party protocol over ad-regular network with a constant mixing time, and in particular for random graphs withvertices and degreesnΩ(1).
登录
查看更多内容
DOI：
10.1109/sfcs.2005.48
发表时间：
2005
期刊：
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
影响因子：
--
作者：
Navin Goyal;Guy Kindler;Michael E. Saks
通讯作者：
Michael E. Saks
针对对抗性噪声的快速交互式编码
DOI：
--
发表时间：
2014
期刊：
JACM
影响因子：
--
作者：
Zvika Brakerski;Y. Kalai;M. Naor
通讯作者：
M. Naor
针对对抗性噪声的高效交互式编码
DOI：
--
发表时间：
2012
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Zvika Brakerski;Y. Kalai
通讯作者：
Y. Kalai
交互式编码的最佳错误率 II：效率和列表解码
DOI：
--
发表时间：
2013
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
Bernhard Haeupler
DOI：
--
发表时间：
1993
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
L. Schulman
通讯作者：
L. Schulman