Wednesday, May 25, 2016 - 12:00pm to 1:00pm
Speaker:BADIH GHAZI, Research Assistant http://people.csail.mit.edu/badih/
Many natural forms of communication involve two (or more) players interacting based on a shared context, where the context is huge and imperfectly shared. This large context typically helps compress communication even when the sharing is imperfect. How can we explain this phenomenon mathematically? In this talk, we will argue that communication complexity gives the right lens to view this class of problems, and this class of problems gives rise to new questions about communication complexity. I will describe some of these questions, some partial answers and some confounding open questions. Based on joint works with Ilan Komargodski, Pravesh Kothari and Madhu Sudan.