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 年代的香农模型和 1970 年代的姚模型。一方面，香农模型带来了丰富的问题​​集合，在没有不确定性的情况下可以充分解决这些问题。另一方面，Yao 模型提出了一种通过设置相关输入来捕获不确定性的自然模型。将两者混合会产生丰富的问题​​，包括：1）当发送者和接收者不确定彼此使用的先验时，信息是否可以被压缩到熵？2）是否可以用轻度相关的随机变量来取代普遍使用的随机性，同时保留沟通的复杂性？3）即使沟通的确切目标存在不确定性，沟通能否保持高效？该项目通过指定捕获问题的精确数学度量，然后分析所得度量来探讨上述问题。

项目成果

Local decoding and testing of polynomials over grids

网格上多项式的本地解码和测试

• DOI: 10.1002/rsa.20933
• 发表时间: 2020-06
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Bafna, Mitali;Srinivasan, Srikanth;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

具有多对数更新时间的全动态最大独立集

• DOI: 10.1109/focs.2019.00032
• 发表时间: 2019-11
• 期刊: {FOCS} 2019
• 作者: Behnezhad, Soheil;Derakhshan, Mahsa;Hajiaghayi, MohammadTaghi;Stein, Cliff;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Communication With Imperfectly Shared Randomness

不完美共享随机性的通信

• DOI: 10.1109/tit.2017.2734103
• 发表时间: 2017-10
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Canonne, Clement L.;Guruswami, Venkatesan;Meka, Raghu;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Tracking the l_2 Norm with Constant Update Time

使用恒定更新时间跟踪 l_2 范数

• DOI: 10.4230/lipics.approx-random.2019.2
• 发表时间: 2019-09
• 期刊: {APPROX/RANDOM} 2019
• 作者: Chou, Chi;Lei, Zhixian;Nakkiran, Preetum
• 通讯作者: Nakkiran, Preetum

Synchronization Strings: List Decoding for Insertions and Deletions

同步字符串：插入和删除的列表解码

• DOI: 10.4230/lipics.icalp.2018.76
• 发表时间: 2018-01
• 期刊: Languages and Programming
• 作者: Haeupler, Bernhard;Shahrasbi, Amirbehshad;Sudan, Madhu
• 通讯作者: Sudan, Madhu