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.

现代通信设备具有巨大的计算和存储信息的能力。这些能力可以提供丰富的潜在方式，以帮助其用户并适应其偏好。不幸的是，这种适应用户的能力在与其他类似设备进行通信时也引入了挑战。现在，每个设备都不确定其他设备的确切知识和行为。该项目探讨了与这种不确定性交流的理论基础。一方面，它专注于定性问题，例如“误解”，并在采取有影响力的行动之前探索如何检测和纠正误解。 另一方面，它还探讨了即使在不确定性的情况下，大型共享环境可以导致高效（短）通信的定量问题。该项目的更广泛的智力影响将来自通信和计算机科学的数学领域与语言学，哲学，神经科学和传播研究等领域之间的扩展联系。科学界也将通过打算从事自己的研究职业的初级研究人员（候选人）的指导和教育来实现更大的影响。教育课程和材料将根据该跨学科研究项目开发。最后，该项目将通过介绍研究及其在领先的会议，研讨会以及学术和工业研究机构的研讨会上的成果以及在公开可公开的网站上发布出版物，从而积极寻求研究进展。 不确定的交流理论的科学基础导致了关于交流模型的问题，该模型是1940年代香农模型的融合，以及1970年代的YAO模型。一方面，香农模型会导致很多问题收集，如果没有不确定性，可以充分解决这些问题。另一方面，YAO模型提出了一种自然模型，用于通过相关输入的设置来捕获不确定性。将两个引物融合到很多问题，包括：1）当发送者和接收者不确定彼此使用的先验时，是否可以将信息压缩到其熵？2）2）无处不在的随机性可以被轻度相关的随机变量所代替，而随机变量可以避免沟通的复杂性，甚至可以远离沟通的问题，即使沟通不确定？捕获问题然后分析结果措施的措施。

项目成果

Round Complexity of Common Randomness Generation: The Amortized Setting

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

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

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

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

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

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