Title:The Landscape of Constant-Cost Randomized Communication Problems
Speaker: Nathaniel Harms (EPFL)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: Wednesday, November 6, 10:00 – 12h30
Where: FCUL, C6.2.33

Abstract: Some of the most extreme examples of the power of randomness in computation come from communication complexity, where non-trivial problems can be solved with constant randomized communication cost (independent of the input size), while the deterministic cost is as large as possible. We wish to understand these examples where randomness is extremely effective.
Intuitively, constant cost seems quite restrictive, so one may expect there to be a simple characterization of this class of problems. Is there, say, a “complete” problem for this class? In this talk we will see that there is no complete problem for this class, and that the k-Hamming Distance problems are not a “complete hierarchy” for this class.
Joint work with Yuting Fang, Mika Goos, Lianna Hambardzumyan, and Pooya Hatami.

Bio: Nathan Harms is a postdoc at EPFL hosted by Mika Goos, and received his PhD from the University of Waterloo advised by Eric Blais. He is interested in fundamental questions about randomized algorithms, including property testing and communication complexity, and he likes to draw pictures.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.