AF: Small: Communication Amid Uncertainty

AF：小：不确定性中的沟通

• 批准号: 1715187
• 负责人: Madhu Sudan
• 金额: $ 45万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1715187&HistoricalAwards=false
• 关键词: AF; Small; Communication; Amid; Uncertainty

Modern communication devices possess enormous ability to compute and to store information. These abilities enable a rich collection of potential ways in which the device can aid its user and adapt to their preferences. Unfortunately, this ability to adapt to the user also introduces challenges when communicating with other similar devices. Each device is now uncertain about the exact knowledge and behavior of the other devices. This project explores the theoretical foundations for communicating with such uncertainty. On the one hand, it focuses on qualitative issues such as "misunderstanding" and explores how misunderstanding can be detected and corrected before influential actions are taken. On the other hand, it also explores the quantitative issues behind how large shared context can lead to efficient (short) communications even in the presence of uncertainty. The broader intellectual impact of the project will come from expanded connections between the mathematical fields of communication and computer science to fields such as linguistics, philosophy, neuroscience, and communication studies. Broader impact among the scientific community will also be achieved by the mentoring and education of junior researchers (Ph.D. candidates) who intend to pursue their own careers in research. Educational courses and materials will be developed based on this interdisciplinary research project. Finally, the project will actively seek broad dissemination of the progress in research by presentation of the research and its outcomes in seminars at leading conferences, workshops, and academic and industrial research institutions, and by posting publications on publicly available websites. The scientific foundations for a theory of uncertain communication lead to questions on a model of communication that is a blend of the Shannon model from the 1940s, and the Yao model from the 1970s. On the one hand, the Shannon model leads to a rich collection of problems that can be solved adequately when there is no uncertainty. The Yao model, on the other hand, presents a natural model for capturing uncertainty via the setting of correlated inputs. Blending the two leads to rich questions including:1) Can information be compressed down to its entropy when sender and receiver are uncertain about the priors used by each other?2) Can the ubiquitous use of randomness be replaced by mildly correlated random variables while conserving the complexity of communication?3) Can communication remain efficient even if there is uncertainty about the exact goal of the communication?This project explores questions such as the above by ascribing precise mathematical measures that capture the questions and then analyzing the resulting measures.

现代通信设备具有巨大的计算和存储信息的能力。这些功能使设备能够以丰富的潜在方式来帮助其用户并适应他们的偏好。不幸的是，这种适应用户的能力在与其他类似设备通信时也带来了挑战。每个设备现在都不确定其他设备的确切知识和行为。这个项目探讨了与这种不确定性沟通的理论基础。一方面，它侧重于“误解”等定性问题，并探讨如何在采取有影响力的行动之前发现和纠正误解。 另一方面，它还探讨了即使在存在不确定性的情况下，大的共享上下文如何能够导致有效（短）的通信背后的定量问题。该项目更广泛的智力影响将来自通信和计算机科学的数学领域与语言学，哲学，神经科学和通信研究等领域之间的联系。对初级研究人员（博士）的指导和教育也将在科学界产生更广泛的影响。候选人）谁打算追求自己的研究事业。教育课程和材料将根据这一跨学科的研究项目开发。最后，该项目将积极寻求广泛传播研究进展，在主要会议、讲习班、学术和工业研究机构的研讨会上介绍研究及其成果，并在公开网站上张贴出版物。 不确定沟通理论的科学基础导致了对沟通模型的质疑，该模型是20世纪40年代的香农模型和20世纪70年代的姚明模型的混合。一方面，香农模型导致了一系列丰富的问题，当不存在不确定性时，这些问题可以得到充分的解决。另一方面，Yao模型提供了一种通过设置相关输入来捕捉不确定性的自然模型。将这两种方法结合起来会产生很多问题，包括：1）当发送者和接收者对彼此使用的先验知识不确定时，信息能否被压缩到熵？2)在保持通信复杂性的同时，随机性的普遍使用是否可以被轻度相关的随机变量所取代？3)即使沟通的确切目标不确定，沟通是否仍然有效？这个项目通过精确的数学测量来探索上述问题，然后分析得到的测量结果。

项目成果

Communication with Contextual Uncertainty

与情境不确定性进行沟通

• DOI: 10.1007/s00037-017-0161-3
• 发表时间: 2018
• 期刊: computational complexity
• 影响因子: 1.4
• 作者: Ghazi, Badih;Komargodski, Ilan;Kothari, Pravesh K.;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Round Complexity of Common Randomness Generation: The Amortized Setting

常见随机性生成的轮复杂度：摊销设置

• DOI: 10.1137/1.9781611975994.66
• 发表时间: 2020
• 期刊: {SODA} 2020
• 作者: Golowich, Noah;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Cell-probe lower bounds from online communication complexity

在线通信复杂性的细胞探针下限

• DOI: 10.1145/3188745.3188862
• 发表时间: 2018
• 期刊: STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing Pages 1003-1012
• 作者: Alman, Josh;Wang, Joshua R.;Yu, Huacheng
• 通讯作者: Yu, Huacheng

Optimal succinct rank data structure via approximate nonnegative tensor decomposition

• DOI: 10.1145/3313276.3316352
• 发表时间: 2018-11
• 期刊: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Huacheng Yu

Optimality of Correlated Sampling Strategies

相关抽样策略的最优性

• DOI: 10.4086/toc.2020.v016a012
• 发表时间: 2020
• 期刊: Theory of Computing
• 影响因子: 1
• 作者: Bavarian, Mohammad;Ghazi, Badih;Haramaty, Elad;Kamath, Pritish;Rivest, Ronald L.;Sudan, Madhu
• 通讯作者: Sudan, Madhu