The probabilistic universal graph conjecture for stable matrix families
The probabilistic universal graph conjecture for stable matrix families
Let be a sequence of Boolean matrices. For a sequence of matrices, let be the set of all square submatrices of matrices in the sequence, and let denote its members. Let denote the randomized communication complexity of the sequence. If is the Greater-Than matrix defined by if and only if , then is stable when for some . Probabilistic Universal Graph Conjecture. One has
if and only if is stable and
The statement is the communication-complexity formulation of the probabilistic version of the Implicit Graph Conjecture proposed by Harms, Wild, and Zamaraev. The paper's abstract states that this conjecture is refuted, so the claimed equivalence is not valid in general.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Lianna Hambardzumyan, Hamed Hatami and Pooya Hatami, “A counter-example to the probabilistic universal graph conjecture via randomized communication complexity”, arXiv:2111.10436 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.