Viðburðir eftir árum

ICE-TCS seminar: Alexandre Nolin

The special case of functions with large outputs in communication complexity

  • 9.3.2020, 11:50 - 12:35

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

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: