Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks
Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks
复制标题
即使在恒定度网络中，恒定速率交互式编码也是不可能的
DOI：
--
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Y. Kalai
中科院分区：
文献类型：
--
作者：
R. Gelles;Y. Kalai
多方交互编码允许一个网络的<inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula>方执行分布式计算时，通信信道受到噪声。以前的结果（Rajagopalan和Schulman，STOC 1994）得到了一个多方交互式编码协议，弹性随机噪声，爆破的<inline-formula><tex-math notation="LaTeX">$O（log（Delta +1））$</tex-math></inline-formula>的网络拓扑结构具有最大程度<inline-formula><tex-math notation="LaTeX">的$Delta $</tex-math></inline-formula>。至关重要的是，他们工作中的通信模型迫使所有各方在每一轮协议中发送一条消息，即使他们没有什么可发送的。我们重新审视多方交互式编码的问题，解除了迫使所有各方在每一轮进行通信的要求。我们使用最近开发的信息理论的机器Braverman<italic>等人。</italic>（J. ACM 2018）表明，如果网络的拓扑结构是一个循环，则存在一个特定的循环任务，对于该任务，任何编码方案都具有<inline-formula><tex-math notation="LaTeX">$Omega（log n）$</tex-math></inline-formula>的通信爆破。这是相当令人惊讶的，因为循环的最大度为<inline-formula><tex-math notation="LaTeX">$Delta =2$</tex-math></inline-formula>，这意味着当所有各方都被迫在所有回合发言时，编码会<italic>不断爆破</italic>。我们补充我们的下限与匹配的编码方案的周期任务，有一个通信爆破的<inline-formula><tex-math notation="LaTeX">$Theta（log n）$</tex-math></inline-formula>。这使得我们的周期任务的下限很紧。
Multiparty interactive coding allows a network of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC 1994) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of <inline-formula> <tex-math notation="LaTeX">$O(log (Delta +1))$ </tex-math></inline-formula> for networks whose topology has a maximal degree <inline-formula> <tex-math notation="LaTeX">$Delta $ </tex-math></inline-formula>. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send. We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman <italic>et al.</italic> (J. ACM 2018) to show that if the network’s topology is a cycle, then there is a specific cycle task for which any coding scheme has a communication blowup of <inline-formula> <tex-math notation="LaTeX">$Omega (log n)$ </tex-math></inline-formula>. This is quite surprising since the cycle has a maximal degree of <inline-formula> <tex-math notation="LaTeX">$Delta =2$ </tex-math></inline-formula>, implying a coding with a <italic>constant blowup</italic> when all parties are forced to speak at all rounds. We complement our lower bound with a matching coding scheme for the cycle task that has a communication blowup of <inline-formula> <tex-math notation="LaTeX">$Theta (log n)$ </tex-math></inline-formula>. This makes our lower bound for the cycle task tight.
通过高度连接的嘈杂网络进行可靠通信
影响因子：
1.3
作者：
Alon, Noga;Braverman, Mark;Efremenko, Klim;Gelles, Ran;Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard