Please note: This seminar will take place in DC 3317 and online.
Mika Goos, Assistant Professor
Department of Computer Science, École Polytechnique Fédérale de Lausanne (EPFL)
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.
This seminar will take place in person (location TBD) and on Zoom.