Communication Complexity with a more-than usal emphasis on Upper Bounds. Part 1 : Setting the stage
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.
