Abstract:

Is it possible for two intelligent players to communicate meaningfully 
with each other, without any prior common background? What does it even 
mean for the two players to understand each other? In addition to being 
an intriguing question in its own right, we argue that this question 
also goes to the heart of modern communication infrastructures, where 
misundestandings (mismatches in protocols) between communicating players 
are a major source of errors. We believe that questions like this need 
to be answered to set the foundations for a robust theory of 
(meaningful) communication.

In this talk, I will describe what computational complexity has to say 
about such interactions. Most of the talk will focus on how some of the 
nebulous notions, such as intelligence and understanding, should be 
defined in concrete settings. We assert that in order to communicate 
``successfully'', the communicating players should be explicit about 
their goals - what the communication should achieve. We show examples 
that illustrate that when goals are explicit the communicating players 
can achieve meaningful communication.

Joint work with Brendan Juba (MIT).