A counter-example to the probabilistic universal graph conjecture via randomized communication complexity.
Lianna HambardzumyanHamed HatamiPooya HatamiPublished in: CoRR (2021)
Keyphrases
- kolmogorov complexity
- worst case
- random walk
- generative model
- directed graph
- computational complexity
- probabilistic logic
- graph theoretic
- graph representation
- graph model
- communication systems
- graph structure
- connected components
- information theoretic
- structured data
- graphical models
- probabilistic model
- belief networks
- bipartite graph
- graph theory
- information sharing
- graph mining
- inductive inference
- graph data
- computational cost
- data sets