Randomized Communication and Implicit Graph Representations

Nathaniel Harms, Sebastian Wild, Viktor Zamaraev

We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…