ICE-TCS seminar: Alexandre Nolin
The special case of functions with large outputs in communication complexity
ICE-TCS seminar #350
Next week we welcome Alexandre Nolin, a new postdoc at RU.
Date and time: Monday, 9 March 2020, 11:50-12:35
Location: Room M108
Speaker: Alexandre Nolin, Reykjavik University, Iceland
Title: The special case of functions with large outputs in communication complexity
Abstract: The two-party communication complexity model is a model of computation where two players want to compute the output of a function whose input is split between them. The players are computationally unbounded and we are only interested in how much communication needs to take place between them.
When studying a Boolean function in this model, it makes very little difference whether both or only one of them have to output the result of the computation. For a function with large outputs, however, the communication complexity of computing it can vary greatly with the "output model" -- the way in which the players have to output the result of their computation.
In this talk, we will revisit some classical results of communication complexity in a few output models. Our main focus will be error reduction schemes. While the naïve adaption of the classical result to our output models would incur an additional cost in the size of the output, we show that this can be avoided in all models. Particularly interesting is the case of the most communication-efficient model, the XOR model, for which our error reduction scheme involves a random graph and an amortized protocol for the Equality problem.
Based on joint work with Lila Fontes, Sophie Laplante, and Matthieu Laurière
