The probabilistic universal graph conjecture for stable matrix families

From papers

Let M\mathcal M be a sequence of n×nn \times n Boolean matrices. For a sequence of matrices, let cl(M)\operatorname{cl}(\mathcal M) be the set of all square submatrices of matrices in the sequence, and let cl(M)n\operatorname{cl}(\mathcal M)_n denote its n×nn \times n members. Let R(M)\operatorname{R}(\mathcal M) denote the randomized communication complexity of the sequence. If GTk\mathrm{GT}_k is the k×kk \times k Greater-Than matrix defined by GTk(i,j)=1\mathrm{GT}_k(i,j)=1 if and only if iji \leq j, then M\mathcal M is stable when GTkcl(M)\mathrm{GT}_k \notin \operatorname{cl}(\mathcal M) for some kNk \in \mathbb N. Probabilistic Universal Graph Conjecture. One has

R(M)=O(1)\operatorname{R}(\mathcal M)=O(1)

if and only if M\mathcal M is stable and

cl(M)n2O(nlogn).|\operatorname{cl}(\mathcal M)_n|\leq 2^{O(n \log n)}.

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

No solutions have been posted yet.