AF: Small: Communication Amid Uncertainty

Harvard University, Cambridge MA

Investigators

Abstract

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.