论文标题
关于有限国家协议的互动能力
On the Interactive Capacity of Finite-State Protocols
论文作者
论文摘要
嘈杂通道的交互能力是可以在通道上可靠地模拟任意交互式协议的最高速率。众所周知，确定互动能力是困难的，最著名的下限远低于相关的香农容量，香农容量是一种微不足道的（也是最著名的）上限。本文考虑了模拟有限状态协议的更受限制的设置。结果表明，所有两国规程以及任意有限国家协议的富裕家族都可以以香农的能力进行模拟，从而为这些协议家族建立互动能力。
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
