CIF: Small: Fundamental limits in ambiguous communication

噪声，无论是来自环境还是由于固有的随机性，都是用于在两方或多方之间传输数据的信息通道的不可避免的特征。这种信道的所谓零差错容量是当允许信道的多次使用时，信息可以以零差错概率经由信道传输的最佳速率。虽然在实践中，噪声的影响随时间而变化，但迄今为止可用的容量理论大多集中在简化的情况下，其中信道的连续使用是独立的。该项目旨在建立理论基础，允许在状态依赖机制中估计零误差容量和密切相关的参数，其中信道的每个单独使用取决于其先前的使用和周围噪声的当前状态。它是使用开发的框架来研究一个特殊的情况下，信息渠道，这被视为策略的游戏-所谓的两个证明者游戏-其中两个球员进行测试，通过一个问答过程，由一个验证者，为共同拥有的某一段知识。直到现在，这种博弈只被认为是在无记忆的情况下进行的，在这种情况下，连续的几轮博弈是相互独立的。该项目研究两个证明者博弈的获胜率，其中参与者和验证者具有记忆，并且博弈规则--被测试的知识--可以随时间而演变。在信息通道的设置中，该项目定义和研究具有记忆的通道的零错误容量，其中包括作为一个特例的无记忆通道的通常零错误容量作为一个一次性参数。这是通过引入状态依赖信道的混淆图来实现的，而该参数的估计和界限是通过开发有限图的著名Lovász数的可测量版本来获得的。在两个证明者游戏的设置中，该项目正在开发具有记忆的玩家之间的无信号相关性，包括有用的子类，例如量子相关性类，作为具有有限问答集的游戏玩家之间的无信号相关性的深远概括。这种方法允许考虑价值分离问题和在一般框架中识别参与者的渐近行为，允许应用功能分析和算子理论工具。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Noise, either arising from the environment or due to inherent randomness, is an unavoidable feature of information channels, which are used to transmit data between two or more parties. So-called zero-error capacities of such channels are the optimal rates at which information can be transmitted via the channel with a zero probability of error when multiple uses of the channel are allowed. While in practice the effects of noise change with time, the capacity theories available until now focus mostly on the simplified picture where the successive uses of the channel are independent. This project aims at establishing the theoretical foundations that would allow the estimation of zero-error capacities and closely related parameters in the state-dependent regime, where each individual use of the channel depends on its previous uses and the current state of the surrounding noise. It is using the developed framework to study a special case of information channels, which are viewed as strategies for games -- called two-prover games -- in which two players are tested by a verifier, through a question-answer process, for the joint possession of a certain piece of knowledge. Such games have until now been considered only in the memoryless situation where the successive rounds of the game are played independently from each other. The project is studying the winning rates of two-prover games, where the players and the verifier possess memory and the rules of the game -- the tested knowledge -- may evolve with time.In the setting of information channels, the project is defining and studying the zero-error capacity of a channel with memory, which covers as a special case the usual zero-error capacity of a memoryless channel as a one-shot parameter. This is being achieved through the introduction of the confusability graph of a state-dependent channel, while estimations and bounds for this parameter are obtained by developing a measurable version of the well-known Lovász number of a finite graph. In the setting of two prover games, the project is developing no-signaling correlations between players with memory, including useful subclasses such as the class of quantum correlations, as a far-reaching generalization of no-signaling correlations between players of games with finite question-answer sets. This approach allows the consideration of value-separation questions and the identification of the players' asymptotic behavior in a general framework, allowing the application of functional analytic and operator theoretic tools.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.