Seminar • Algorithms and Complexity • Randomness Without Randomness: Structural Explanations of the Power of Randomness in Communication

Please note: This seminar will take place in DC 1304 and online.

Nathan Harms, Postdoctoral Researcher
École polytechnique fédérale de Lausanne, Switzerland

Understanding the power of randomness in communication is one of the main goals in communication complexity. Towards this goal, many recent works have studied constant-cost communication problems, which are the most extreme cases of the power of randomized communication. In this talk I will survey some of these works and discuss several results which present structural explanations for the power of certain constant-cost randomized protocols.

To attend this seminar in person, please go to DC 1304. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/98726302143.