Randomized communication and implicit graph representations

DOI10.1145/3519935.3519978MaRDI QIDQ6083575zbMATH OpenFDO

Authors Nathaniel Harms, Sebastian Wild, Victor Zamaraev

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03639

zbMATH Keywords

adjacency labeling schemeimplicit graph conjecturerandomized communication protocols

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 $mathcalF$ 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 $mathcalHsubseteqmathcalF$ are either stable (in a sense relating to model theory), in which case they admit constant-size PUGs, or they are not stable, in which case they do not. 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 $mathsfdist(x,y)lek$ 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.

Cited in

(9)

• scientific article; zbMATH DE number 4051664 (Why is no real title available?)
• Optimal adjacency labels for subgraphs of Cartesian products
• Small but unwieldy: a lower bound on adjacency labels for small classes
• A hierarchy of constant communication complexity
• Factorization norms and an inverse theorem for MaxCut
• Tight bounds on adjacency labels for monotone graph classes
• Randomized communication and implicit graph representations
• Better boosting of communication oracles, or not
• Equality is far weaker than constant-cost communication

This page was built for publication: Randomized communication and implicit graph representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083575)