Randomized communication and implicit graph representations

DOI10.46298/THEORETICS.25.20MaRDI QIDQ6912581zbMATH OpenFDO

Authors Nathaniel Harms, Sebastian Wild, Victor Zamaraev

Publication date 22 October 2025

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.25.20

zbMATH Keywords

adjacency labeling schemesadjacency sketchesconstant-cost protocolshereditary graph classesimplicit graph representationsprobabilistic universal graphsrandomized communication complexity

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Applications of graph theory (05C90) Communication theory (94A05)

Cites work

• A Borsuk-Ulam lower bound for sign-rank and its applications
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• A jump to the Bell number for hereditary graph properties
• A note on the Erdős-Hajnal property for stable graphs
• A Ramsey-type result for the hypercube
• A SAT approach to twin-width
• Adjacency Labelling for Planar Graphs (and Beyond)
• Adjacency sketches in adversarial environments
• Bounds for the twin-width of graphs
• Communication Complexity
• Communication Complexity
• Communication complexity and discrepancy of halfplanes
• Complexity measures and decision tree complexity: a survey.
• Covering graphs by the minimum number of equivalence relations
• Deciding the Bell number for hereditary graph properties
• Dimension-free bounds and structural results in communication complexity
• Efficient graph representations
• Equality alone does not simulate randomness
• Exponential separation of quantum communication and classical information
• Forbidden induced bipartite graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Handbook of product graphs
• Handle-rewriting hypergraph grammars
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• scientific article; zbMATH DE number 7650381 (Why is no real title available?)
• scientific article; zbMATH DE number 7788458 (Why is no real title available?)
• scientific article; zbMATH DE number 7803584 (Why is no real title available?)
• Implicat Representation of Graphs
• Implicit representation conjecture for semi-algebraic graphs
• Implicit representations and factorial properties of graphs
• Local representations using very short labels
• Logical labeling schemes
• Lower bound methods for sign-rank and their limitations
• Near log-convexity of measured heat in (discrete) time and consequences
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• On a product dimension of graphs
• On data structures and asymmetric communication complexity
• On density of subgraphs of Cartesian products
• On randomized one-round communication complexity
• On the power of quantum fingerprinting
• On the size of hereditary classes of graphs
• Optimal adjacency labels for subgraphs of Cartesian products
• Private vs. common random bits in communication complexity
• Probabilistic communication complexity
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Randomized communication and implicit graph representations
• Range of values of the entropy of hereditary classes of graphs
• Regularity lemmas for stable graphs
• Separation of the factorization norm and randomized communication complexity
• Sketching distances in monotone graph classes
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Sphere and dot product representations of graphs
• Stable graphs of bounded twin-width
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The communication complexity of addition
• The communication complexity of the Hamming distance problem
• The implicit graph conjecture is false
• The landscape of communication complexity classes
• The speed of hereditary properties of graphs
• The structure and the number of \(P_7\)-free bipartite graphs
• Tight bounds on adjacency labels for monotone graph classes
• Twin-width can be exponential in treewidth
• Twin-width II: small classes
• Twin-width. I: Tractable FO model checking
• Universal graphs and universal functions
• Words and graphs

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 Q6912581)