Towards Universal Semantic Communication Madhu Sudan (MSR New England) 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? We claim that this question, in addition to being of philosophical/linguistic interest, goes to the essence of modern communication/computation. Modern communicating devices are extremely diverse, constantly evolving, and misunderstandings (mismatches in protocols) between communicating devices are inevitable and a major source of errors. The questions raised above need to be answered to set the foundations for a robust theory of (meaningful) communication - one that would cover such diverse & evolving communicating devices. In this talk, I will describe our approach towards this problem. We argue that in order to get to the heart of such questions, one must first articulate why intelligent players (and/or powerful computers) communicate. This leads us to a formal theory of "goals" of communication. We then show that when progress towards the goal is "verifiable'' then players can detect misunderstandings. Under a complexity-theoretic lens, we show roughly that verifiability is really the essence of resolving misunderstandings: Verifiable goals are more powerful than goals that can be achieved without communication (so communication is good), but very restricted compared to ``unverifiable'' goals (so there is need for moderation). Most of the talk will focus on the definitions of various concepts such as ``goals'', ``(mis)understanding'' and resort to theorems based on computational complexity to support these definitions. Based on joint works with Oded Goldreich (Weizmann) and Brendan Juba (MIT)