Document Open Access Logo

Universal Communication, Universal Graphs, and Graph Labeling

Author Nathaniel Harms

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.33.pdf
  • Filesize: 0.6 MB
  • 27 pages

Document Identifiers

Author Details

Nathaniel Harms
  • University of Waterloo, Canada

Funding

  • Harms, Nathaniel: This research partially supported by the David R. Cheriton and GO-Bell Graduate Scholarships.

Acknowledgements

Thanks to Eric Blais for comments on the structure of this paper; Amit Levi for helpful discussions and comments on the presentation; Anna Lubiw for an introduction to planar graphs and graph labeling; Corwin Sinnamon for comments on distributive lattices; and Sajin Sasy for observing the possible applications to privacy.

Cite AsGet BibTex

Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 33:1-33:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.33

Abstract

We introduce a communication model called universal SMP, in which Alice and Bob receive a function f belonging to a family ℱ, and inputs x and y. Alice and Bob use shared randomness to send a message to a third party who cannot see f, x, y, or the shared randomness, and must decide f(x,y). Our main application of universal SMP is to relate communication complexity to graph labeling, where the goal is to give a short label to each vertex in a graph, so that adjacency or other functions of two vertices x and y can be determined from the labels ℓ(x), ℓ(y). We give a universal SMP protocol using O(k^2) bits of communication for deciding whether two vertices have distance at most k in distributive lattices (generalizing the k-Hamming Distance problem in communication complexity), and explain how this implies a O(k^2 log n) labeling scheme for deciding dist(x,y) ≤ k on distributive lattices with size n; in contrast, we show that a universal SMP protocol for determining dist(x,y) ≤ 2 in modular lattices (a superset of distributive lattices) has super-constant Ω(n^{1/4}) communication cost. On the other hand, we demonstrate that many graph families known to have efficient adjacency labeling schemes, such as trees, low-arboricity graphs, and planar graphs, admit constant-cost communication protocols for adjacency. Trees also have an O(k) protocol for deciding dist(x,y) ≤ k and planar graphs have an O(1) protocol for dist(x,y) ≤ 2, which implies a new O(log n) labeling scheme for the same problem on planar graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Trees
  • Theory of computation → Models of computation
  • Theory of computation → Communication complexity
  • Theory of computation → Computational geometry
  • Theory of computation → Generating random combinatorial structures
Keywords
  • Universal graphs
  • graph labeling
  • distance labeling
  • planar graphs
  • lattices
  • hamming distance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Geir Agnarsson and Magnús M Halldórsson. Coloring powers of planar graphs. SIAM Journal on Discrete Mathematics, 16(4):651-662, 2003. Google Scholar
  2. Stephen Alstrup, Philip Bille, and Theis Rauhe. Labeling schemes for small distances in trees. SIAM Journal on Discrete Mathematics, 19(2):448-462, 2005. Google Scholar
  3. Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM (JACM), 64(4):27, 2017. Google Scholar
  4. Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear distance labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  5. Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat. Distance labeling schemes for trees. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016. Google Scholar
  6. Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs. SIAM Journal on Discrete Mathematics, 33(1):116-137, 2019. Google Scholar
  7. Tiziana Calamoneri. The L(h,k)-Labelling Problem: An Updated Survey and Annotated Bibliography. The Computer Journal, 54(8):1344-1371, 2011. Google Scholar
  8. Clément L Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan. Communication with imperfectly shared randomness. IEEE Transactions on Information Theory, 63(10):6799-6818, 2017. Google Scholar
  9. Nathalie Caspard, Bruno Leclerc, and Bernard Monjardet. Finite Ordered Sets: Concepts, Results and Uses. Cambridge University Press, 2012. Google Scholar
  10. Maurice Chandoo. On the implicit graph conjecture. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58, page 23. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  11. Stefan Felsner. Geometric graphs and arrangements: some chapters from combinatorial geometry. Springer, 2012. Google Scholar
  12. Pierre Fraigniaud and Amos Korman. On randomized representations of graphs using short labels. In Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures, pages 131-137. ACM, 2009. Google Scholar
  13. Pierre Fraigniaud and Amos Korman. An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets. Journal of the ACM, 63(1):6, 2016. Google Scholar
  14. Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In European Symposium on Algorithms, pages 582-593. Springer, 2007. Google Scholar
  15. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of algorithms, 53(1):85-112, 2004. Google Scholar
  16. Paweł Gawrychowski and Przemysław Uznański. A note on distance labeling in planar graphs, 2016. URL: http://arxiv.org/abs/1611.06529.
  17. Badih Ghazi, Ilan Komargodski, Pravesh Kothari, and Madhu Sudan. Communication with Contextual Uncertainty. Computational Complexity, 27(3):463-509, 2018. Google Scholar
  18. Badih Ghazi and Madhu Sudan. The power of shared randomness in uncertain communication. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 49:1-49:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  19. Oded Goldreich, Brendan Juba, and Madhu Sudan. A theory of goal-oriented communication. Journal of the ACM, 59(2):8, 2012. Google Scholar
  20. Elad Haramaty and Madhu Sudan. Deterministic compression with uncertain priors. Algorithmica, 76(3):630-653, 2016. Google Scholar
  21. Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the Hamming distance problem. Information Processing Letters, 99(4):149-153, 2006. Google Scholar
  22. Ross J Kang and Tobias Müller. Sphere and dot product representations of graphs. Discrete & Computational Geometry, 47(3):548-568, 2012. Google Scholar
  23. Sempath Kannan, Moni Naor, and Steven Rudich. Implicit Representations of Graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992. Google Scholar
  24. Haim Kaplan and Tova Milo. Short and Simple Labels for Small Distances and Other Functions. In Workshop on Algorithms and Data Structures, pages 246-257. Springer, 2001. Google Scholar
  25. Peter Bro Miltersen, Noam Nisan, Schmuel Safra, and Avi Wigderson. On data structures and asymmetric communicaton complexity. Journal of Computer and System Sciences, 57(1):37-49, 1998. Google Scholar
  26. J Ian Munro and Corwin Sinnamon. Time and space efficient representations of distributive lattices. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 550-567. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  27. Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, and Dan Boneh. Location privacy via private proximity testing. In NDSS, volume 1, 2011. Google Scholar
  28. Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67-71, 1991. Google Scholar
  29. David Peleg. Informative Labeling Schemes for Graphs. Theoretical Computer Science, 340(3):577-593, 2005. Google Scholar
  30. Richard Rado. Universal graphs and universal functions. Acta Arithmetica, 4(9):331-340, 1964. Google Scholar
  31. Mert Sağlam. Near log-convexity of measured heat in (discrete) time and consequences. In 59th Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 967-978. IEEE, 2018. Google Scholar
  32. Walter Schnyder. Planar graphs and poset dimension. Order, 5(4):323-343, 1989. Google Scholar
  33. Jeremy P Spinrad. Efficient Graph Representations. American Mathematical Society, 2003. Google Scholar
  34. Andrew C.C. Yao. Some complexity questions related to distributive computing. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pages 209-213. ACM, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact