Communication Complexity with a more-than usal emphasis on Upper Bounds. Part 2 : The Information Complexity Paradigm
Appears in collection : 2016 - T1 - WS4 - Inference problems theme
This will be a tutorial-style (long) talk, giving an overview of the important basic results in communication complexity, with emphasis on results that can be seen (sometimes creatively) as designing efficient protocols for certain tasks. As we shall see, a number of lower bounds in communication complexity are also ultimately based on designing protocols.
