Harms, Nathaniel, Wild, Sebastian 
ORCID: 0000-0002-6061-9177 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2021)
Randomized Communication and Implicit Graph Representations.
.
|
Text
2111.03639v1.pdf - Submitted version Download (1MB) | Preview |
Abstract
We study constant-cost randomized communication problems and relate them 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). We initiate the study of the hereditary graph families that admit constant-size PUGs, with the two (equivalent) goals of (1) understanding randomized constant-cost communication problems, and (2) understanding a probabilistic version of the IGQ. For each family $\mathcal 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 $\mathcal H \subseteq \mathcal F$ admit constant-size PUGs (i.e. adjacency sketches) if and only if they are stable (i.e. they forbid a half-graph as a semi-induced subgraph). The correspondence between communication problems and hereditary graph families allows for a new method of constructing adjacency labeling schemes. By this method, we show that the induced subgraphs of any Cartesian products are positive examples to the IGQ. We prove that this probabilistic construction cannot be derandomized by using an Equality oracle, i.e. the Equality oracle cannot simulate the k-Hamming Distance communication protocol. We also obtain constant-size sketches for deciding $\mathsf{dist}(x, y) \le k$ for vertices $x$, $y$ in any stable graph family with bounded twin-width. This generalizes to constant-size sketches for deciding first-order formulas over the same graphs.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 72 pages, 10 figures. Abstract shortened for arXiv |
| Uncontrolled Keywords: | cs.DS, cs.DS, cs.CC, cs.DM |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Nov 2021 07:59 |
| Last Modified: | 22 Jul 2023 06:56 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3143167 |
Share
Share
