Randomized Communication and Implicit Graph Representations

Breaking news! [2021-11-29]

The Implicit Graph Conjecture is false!

Over the course of the last week, Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami first published a counter example to our probabilistic universal graph conjecture (Conjecture 1.2), based on earlier communication complexity result of theirs [HHH21, Theorem 9], which Hatami & Hatami then modified into a counter example for the Implicit Graph Conjecture (IGC)!

Although probabilistic universal graphs (PUGs) did not ultimately play a role in a technical sense in the refutation of the IGC, our connection between adjacency labeling schemes of graphs and communication complexity seems to have inspired the authors to this exciting breakthrough. Similarly, albeit now proven wrong, our PUG conjecture seems to have been a good question to provoke progress.

Adjacency sketches

We study a randomized version of adjacency labeling schemes for families of graphs. We ask specifically: For which hereditary graph families are vertex labels $\ell:V\to{0,1}^\star$ (an adjacency sketch) of constant size enough to decide the adjacency or non-adjacency of two vertices $u$ and $v$ using only $\ell(u)$ and $\ell(v)$ with constant error probability?

We show that this question is equivalent to asking which Boolean functions can be computed with a constant-cost randomized (public coin, two-way) communication protocol and that it has deep connections to the long-standing Implicit Graph Conjecture of structural graph theory.

Background

Two classic problems in communication complexity are EQUALITY and GREATER-THAN, where Alice and Bob each receive a number $x$ resp. $y$ in $[n]$ and then need to decide whether their numbers are equal, $x=y$, resp. whether $x>y$. While hashing gives an easy constant-cost randomized protocol for EQUALITY, GREATER-THAN provably does not allow such a protocol (see Appendix C). Indeed, a binary search for the length of the longest common prefix of the binary representation of $x$ and $y$, using EQUALITY as a subroutine, gives the optimal complexity of $\Theta(\log\log n)$.

This dichotomy translates to graph families that don’t contain resp. do contain a “Greater-than graph” of arbitrary size; making the family either stable or not stable. A family can only have a constant-size adjacency sketch if it is stable. The Constant-PUG Conjecture (Conjecture 1.2) states that containing such a Greater-than instance is also the only barrier to constant-size adjacency sketches.

We confirm this conjecture for many well-known classes of graphs.

Adjacency sketches as data structures

From a data structures perspective, our question can be paraphrased as “What are the limitations of (Bloom) filters for distributed encodings of adjacency in a graph?”. Unfortunately, standard filters with one-sided errors (some false positives, but no false negatives) are inherently limited: they fail even on co-paths ([FK09, Theorem 4]).

Our adjacency sketches therefore allow two-sided errors in the query; effectively allowing the use of filters for the complement set. We formalize this notion as the equality-based labeling schemes (Definition 2.5), and show that (a) two-sided error filters are surprisingly versatile since a huge and rich subset of graph families admits a constant-size equality-based labeling scheme, but (b) that there are constructions for constant-size adjacency sketches that can provably not be simulated using Bloom filters (Theorem 1.18).