A counter-example to the probabilistic universal graph conjecture via randomized communication complexity.
Lianna HambardzumyanHamed HatamiPooya HatamiPublished in: Discret. Appl. Math. (2022)
Keyphrases
- graph representation
- random walk
- space complexity
- worst case
- kolmogorov complexity
- graph structure
- graph theory
- communication networks
- directed graph
- uncertain data
- computer networks
- connected components
- communication overhead
- complexity measures
- data sets
- posterior probability
- context sensitive
- bipartite graph
- structured data
- probabilistic logic
- decision forest