A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
2021
We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal graph if and only if it is stable and has at most factorial speed.
Our counter-example follows from the existence of a sequence of $n \times n$ Boolean matrices $M_n$, such that their public-coin randomized communication complexity tends to infinity, while the randomized communication complexity of every $n^{1/4}\times n^{1/4}$ submatrix of $M_n$ is bounded by a universal constant.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
8
References
0
Citations
NaN
KQI