Harms, Nathaniel, Wild, Sebastian 
ORCID: 0000-0002-6061-9177 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2022)
Randomized Communication and Implicit Graph Representations.
In: STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing.
Abstract
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(logn), which are the subject of the well-studied implicit graph question (IGQ). We initiate the study of the hereditary graph families that admit constant-size PUGs, with the two (equivalent) goals of (1) giving a structural characterization of randomized constant-cost communication problems, and (2) resolving a probabilistic version of the IGQ. For each family F studied in this paper (including the monogenic bipartite families, product graphs, interval and permutation graphs, families of bounded twin-width, and others), it holds that the subfamilies H † F are either stable (in a sense relating to model theory), in which case they admit constant-size PUGs (i.e. adjacency sketches), or they are not stable, in which case they do not. The correspondence between communication problems and hereditary graph families allows for a probabilistic method of constructing adjacency labeling schemes. By this method, we show that the induced subgraphs of any Cartesian products Gd are positive examples to the IGQ, also giving a bound on the number of unique induced subgraphs of any graph product. We prove that this probabilistic construction cannot be "naïvely derandomized"by using an Equality oracle, implying that the Equality oracle cannot simulate the k-Hamming Distance communication protocol. As a consequence of our results, we obtain constant-size sketches for deciding dist(x,y) ≤ k for vertices x,y in any stable graph family with bounded twin-width, answering an open question about planar graphs from earlier work. This generalizes to constant-size sketches for deciding first-order formulas over the same graphs.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | implicit graph conjecture, adjacency labeling scheme, randomized communication protocols |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 14 Jul 2022 12:34 |
| Last Modified: | 27 Nov 2023 21:05 |
| DOI: | 10.1145/3519935.3519978 |
| Open Access URL: | https://arxiv.org/abs/2111.03639 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3158470 |
Dimensions
Dimensions
