The classical theory of communication assumes perfect coordination between sender and receiver of information, to develop a beautiful mathematical theory that ensures reliable efficient communication.  Natural communication, for example, between humans, is however characterized by a lack of perfect agreement among the communicating players. Arguably the uncertainty created by lack of perfect agreement plays a significant role in the development of human languages, which tend to have bendable rules, ambiguous dictionaries, and seemingly needless redundancies, phenomena that are not seen in ``designed communication''.  In this talk we describe how some of the basic communication tasks take on new flavors when dealing with such uncertainty and describe some of mathematical problems that emerge.   Based on joint works with Elad Haramaty (Technion),  Brendan Juba (Harvard), Adam Kalai (MSR), and Sanjeev Khanna (U.Penn.).