Appears in collection : 2016 - T1 - WS1 - Distributed computation and communication theme

Communication complexity had a profound impact on nearly every field of theoretical computer science, and is one of the rare methods for proving unconditional lower bounds. Developing new tools in communication complexity is therefore vital for making progress in other computational models, such as circuit complexity, streaming algorithms, property testing, data structures and VLSI chip design. In this 3-hour mini-course, I will give an introduction to Information Complexity, an interactive analogue of Shannon's information theory, which has recently found many applications in theoretical computer science and in particular for understanding the limitations of parallel computing. Such applications give rise to the fascinating problem of compressing interactive protocols, which will be at the core of this seminar. I will survey some of the exciting recent progress in the field, and some applications of information complexity to parallel computing and secure computation. No prior knowledge will be assumed in this talk.