Randomized communication and implicit graph representations

The most basic lower-bound question in randomized communication complexity is: Does a given problem have constant cost, or non-constant cost? We observe that this question has a deep connection to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O (log n ), which are the subject of the well-studied implicit graph question (IGQ).

Authors

• Nathaniel Harms
• Sebastian Wild
• Viktor Zamaraev

Keywords

• adjacency labeling scheme
• implicit graph conjecture
• randomized communication protocols