CIF: Small: Fundamental limits in ambiguous communication

CIF：小：模糊沟通的基本限制

• 批准号: 2115071
• 负责人: Ivan Todorov
• 金额: $ 18.26万
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2115071&HistoricalAwards=false
• 关键词: CIF; Small; Fundamental; limits; ambiguous

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.

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

项目成果

Information theoretic parameters of noncommutative graphs and convex corners

非交换图和凸角的信息论参数

• DOI: 10.1215/00192082-9799163
• 发表时间: 2022-06
• 期刊: Illinois Journal of Mathematics
• 影响因子: 0.6
• 作者: Boreland, Gareth;Todorov, Ivan G.;Winter, Andreas
• 通讯作者: Winter, Andreas