Communication with Functional Uncertainty

Madhu Sudan (Harvard)

Modern computers are increasingly interacting more like humans do: They incorporate massive context into their communication; and assume that a lot of this context is shared, even if somewhat imprecisely, by other devices they interacts with.  Communications are typically short, and the context often enables this brevity despite it being imperfectly shared. Most of these interactions have gone unstudied mathematically: Indeed it is still unclear as to what is the right model to express and study some of these problems.

In a recent sequence of works we have suggested that these questions are best studied in the "communication complexity" model of Yao: Here two interacting agents "Alice" and "Bob" have private information x and y respectively and interact to compute some joint function f(x.y). Allowing the context to be part of x and y suggests ways in which imperfectly shared context can be incorporated into the study of communication. The abundance of functions f for which f(x,y) can be determined with relatively little communication can be viewed as a positive feature of the model. 

In this talk I will describe some of the above concerns and conclusions in greater detail, before moving on to study yet another source of uncertainty: What happens if Alice and Bob don't even agree on the function f(x,y) being computed? I will describe some positive and negative results.

Based on joint work with Badih Ghazi, Ilan Komargodski and Pravesh Kothari.