Semantic Communication Madhu Sudan (based on joint work with Brendan Juba (MIT); and upcoming work with Oded Goldreich (Weizmann) & J. ) My research interests Computation Communication Role of errors Probabilistically checkable proofs List-decoding and now Semantic Communication
Semantic Communication Bits (words) have meaning Can we preserve meaning when communicating? A Freez e Important B
or in modern society of computers What is meaning? Send 0010000110 Reciever: Recd 0010000110 Did this preserve meaning? No Meaning = Interpretation associated with bits
= how bits recd change state of your mind. (same diff. as between algorithm, and its encoding in some programming language/universal TM) But if no one can read the state of your mind, how do I know if youve misunderstood me? Semantic Communication Definition of Meaning non-trivial Want to preserve it only to the extent that it is relevant.
But relevance should not be defined to make everything irrelevant. If communication achieves some goal with knowledge of language, it should still achieve it without knowledge of language. Our research Part 1 Articulate one class of informationoriented goal of communication. Show how it captures semantic
miscommunication Theorem: If helpful parties interact, they can achieve the goal (while overcoming linguistic hurdles) provided the goal is verifiable. Crux of theorem: Definitions that make it true! Goal=? Bob wants to solve hard computational problem is program P = virus? Is game of chess winnable?
Alien capable of solving hard problem; but doesnt know Bs language. Can A help B? For which Philosophical interpretation of answers If A can only help B solve problems he can solve by himself communication
is pointless. If A can help B solve all problems, communication is powerful and misunderstandings can always be overcome. If A can help B solve some new problems, then communication is ocassionally helpful; and one ought to be careful with it. Misunderstandings and Helpfulness. Modelled by collection of {A}s and {B}s.
(for every language, there is a copy A that speaks in language i, and a B that speaks i). Helpful = For every A there exists B j, such that A helps Bj solve problem (plus technicalities). Universality = B should be able solve problem with every (helpful) Aj. Theorems: B
can use {A}s help to solve every verifiable problem [Verifiable problems include (PSPACEcomplete) problems that B could not solve on its own] B can only solve verifiable problems. [Moral: danger in updating OS and anti-virus software asynchronously.] Our research Part II (ongoing)
Generalize to arbitrary goals of communication. Tricky part: Capturing goal (= state of my mind?) while allowing my actions to vary (in effect changing my mental action and hence states).
