{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:12:27Z","timestamp":1759335147272,"version":"build-2065373602"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,7,18]]},"abstract":"<jats:p>We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communication problems are equivalent to hereditary (i.e. closed under taking induced subgraphs) graph classes which admit constant-size adjacency sketches and probabilistic universal graphs (PUGs), which are randomized versions of the well-studied adjacency labeling schemes and induced-universal graphs. This gives a new perspective on long-standing questions about the existence of these objects, including new methods of constructing adjacency labeling schemes.   We ask three main questions about constant-cost communication, or equivalently, constant-size PUGs: (1) Are there any natural, non-trivial problems aside from Equality and k-Hamming Distance which have constant-cost communication? We provide a number of new examples, including deciding whether two vertices have path-distance at most k in a planar graph, and showing that constant-size PUGs are preserved by the Cartesian product operation. (2) What structures of a problem explain the existence or non-existence of a constant-cost protocol? We show that in many cases a Greater-Than subproblem is such a structure. (3) Is the Equality problem complete for constant-cost randomized communication? We show that it is not: there are constant-cost problems which do not reduce to Equality.<\/jats:p><jats:p>81 pages. This is the TheoretiCS journal version<\/jats:p>","DOI":"10.46298\/theoretics.25.20","type":"journal-article","created":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T07:20:14Z","timestamp":1759303214000},"source":"Crossref","is-referenced-by-count":0,"title":["Randomized Communication and Implicit Graph Representations"],"prefix":"10.46298","volume":"Volume 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0259-9355","authenticated-orcid":false,"given":"Nathaniel","family":"Harms","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6061-9177","authenticated-orcid":false,"given":"Sebastian","family":"Wild","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5755-4141","authenticated-orcid":false,"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2025,10,1]]},"container-title":["TheoretiCS"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2111.03639v6","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2111.03639v6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T07:20:14Z","timestamp":1759303214000},"score":1,"resource":{"primary":{"URL":"https:\/\/theoretics.episciences.org\/11607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,1]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/theoretics.25.20","relation":{"has-preprint":[{"id-type":"arxiv","id":"2111.03639v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2111.03639v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2111.03639","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2111.03639","asserted-by":"subject"}]},"ISSN":["2751-4838"],"issn-type":[{"type":"electronic","value":"2751-4838"}],"subject":[],"published":{"date-parts":[[2025,10,1]]},"article-number":"11607"}}