Adjacency Sketches in Adversarial Environments

An adjacency sketching or implicit labeling scheme for a family F of graphs is a method that defines for any n vertex G ∈ F an assignment of labels to each vertex in G, so that the labels of two vertices tell you whether or not they are adjacent. The goal is to come up with labeling schemes that use as few bits as possible to represent the labels. By using randomness when assigning labels, it is sometimes possible to produce adjacency sketches with much smaller label sizes, but this comes at the cost of introducing some probability of error. Both deterministic and randomized labeling schemes have been extensively studied, as they have applications for distributed data structures and deeper connections to universal graphs and communication complexity. The main question of interest is which graph families have schemes using short labels, usually O(log n) in the deterministic case or constant for randomized sketches.

In this work we consider the resilience of probabilistic adjacency sketches against an adversary making adaptive queries to the labels. This differs from the previously analyzed probabilistic setting which is "one shot". We show that in the adaptive adversarial case the size of the labels is tightly related to the maximal degree of the graphs in F . This results in a stronger characterization compared to what is known in the non-adversarial setting. In more detail, we construct sketches that fail with probability ε for graphs with maximal degree d using 2d log(1/ε) bit labels and show that this is roughly the best that can be done for any specific graph of maximal degree d, e.g. a d-ary tree.