Computer Sciences Colloquium: Interactive Information Theory

Abstract: 

TIn a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the study of error correcting codes and data compression, two concepts that are especially relevant today with the rise of the internet and data-intensive applications. In the last decades, interactive communication protocols are used and studied extensively, raising the fundamental question: To what extent can Shannon's results be generalized to the interactive setting, where parties engage in an interactive communication protocol? In this talk we will focus on the interactive analog of data compression in an attempt to answer the above question. Bio: I am a postdoc fellow in the theoretical computer science group at the Institute for Advanced Study (IAS), Princeton. My research is in complexity theory. I am currently very interested in application of information theory to theoretical computer science, especially to communication complexity. Prior to joining the IAS, I completed a short postdoc at the Technion, received a Ph.d. and M.Sc. from the Weizmann Institute, and a B.A. from the Open University of Israel.