CS Colloquium: Distinguished Speaker Series: Madhu Sudan (Harvard)
Communication Amid Uncertainty
One of the basic goals of the theory of computing is to model behaviour of “intelligent” systems (computers or humans). Behaviour includes ability to acquire information (or knowledge), analyzing it (or reasoning) and communicating it. The theories of Turing (universal computation) and Shannon (reliable communication) offer the foundations for this study covering much of the terrain. And the remarkable progress in the technologies of computing and communication is a testament to the success of these theories. Unfortunately this success has also exposed problems in the intersection of the two fields that neither captures adequately. In our work on “communication amid uncertainty” we explore some such problems, where the ability of two communicating entities to compute allows them to acquire large *mostly* common context. The commonality of the context should enable communication to be even more efficient. On the other hand the “uncertainty” about the context (the fact the context is only mostly common) leads to novel mathematical questions that challenge the fundamental aspects of the classical theories. In this talk we will briefly describe some of the questions and our (partial) answers in this setting of communication with uncertainty.
Google scholar: https://scholar.google.com/citations?user=D-RwB3YAAAAJ&hl=en