Constant-Cost Randomised Communication - Mika Göös (EPFL Lausanne)

Constant-Cost Randomised Communication - Mika Göös (EPFL Lausanne)
Some of the most extreme examples of the power of randomness in computing come from communication complexity, where shared randomness can allow two parties to solve non-trivial problems with communication cost independent of the input size. The textbook example is the Equality problem, where two parties hold n-bit strings x and y, respectively, and they wish to decide whether x = y. While n bits of deterministic communication are necessary, there is a randomised protocol that communicates only 2 bits. Can we characterise all communication problems that admit such hyperefficient protocols? We discuss recent progress and open problems.
Based on joint work with Yuting Fang, Nathaniel Harms, and Pooya Hatami.
____________________
In the context of the "Probabilities in Theoretical Computer Science" Year 2023-24 of GDR IFM, a one-day conference who took place in 2024 at the IHP. The event featured seven invited talks.