Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-075 | 2nd April 2010 14:09

A Theory of Goal-Oriented Communication

RSS-Feed




Revision #1
Authors: Oded Goldreich, Brendan Juba, Madhu Sudan
Accepted on: 2nd April 2010 14:09
Downloads: 1660
Keywords: 


Abstract:

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this context, ``reliable communication'' means overcoming the (potential) initial misunderstanding between parties towards achieving a given goal.

We identify a main concept, which we call sensing, that captures the party's ability to check whether progress is made towards achieving the goal. We then show that if sensing is available, then the gap between a priori mutual understanding and lack of it can be bridged. For example, if providing the parties with an adequate interpreter allows them each to achieve their (possibly different) goals, then they can achieve their goals also without such an interpreter (although they may misunderstand each other and err at the beginning). Or, if each server (in a predetermined class of servers) can help some user (who understands the server) achieve its goal, then there exists a user strategy that achieves the goal no matter with which server it communicates.



Changes to previous version:

Adding advanced topics in Sections 5--7,
plus various corrections.


Paper:

TR09-075 | 17th September 2009 06:28

A Theory of Goal-Oriented Communication





TR09-075
Authors: Oded Goldreich, Brendan Juba, Madhu Sudan
Publication: 17th September 2009 11:59
Downloads: 2139
Keywords: 


Abstract:

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this context, ``reliable communication'' means overcoming the (potential) initial misunderstanding between parties towards achieving a given goal.

We identify a main concept, which we call sensing, that captures the party's ability to check whether progress is made towards achieving the goal. We then show that if sensing is available, then the gap between a priori mutual understanding and lack of it can be bridged. For example, if providing the parties with an adequate interpreter allows them each to achieve their (possibly different) goals, then they can achieve their goals also without such an interpreter (although they may misunderstand each other and err at the beginning). Or, if each server (in a predetermined class of servers) can help some user (who understands the server) achieve its goal, then there exists a user strategy that achieves the goal no matter with which server it communicates.


Comment(s):

Comment #1 to TR09-075 | 12th November 2009 09:19

Typo in the proof of Thm 4.26

Authors: Oded Goldreich
Accepted on: 12th November 2009 09:19
Keywords: 


Comment:

In the beginning of the proof $S$ should be $S^*$, and at the end $\tilde S$ should be defined as a hybrid of $S^*$ and $unpad(S)$.
Details will appear in a forthcoming revision.




ISSN 1433-8092 | Imprint