The log-rank conjecture for deterministic communication
For a Boolean matrix $M \in \{0,1\}^{m \times n}$, known to both players, let $D(M)$ be its deterministic communication complexity: the least number of bits, in the worst case over all pairs $(i, j)$, that Alice, given a row index $i$, and Bob, given a column index $j$, must exchange in a deterministic protocol after which both know $M_{ij}$. Local computation is free, and $\operatorname{rank}_{\mathbb{R}} M$ is the exact rank over the reals. Lovett proved $D(M) = O(\sqrt{r}\,\log r)$ for Boolean matrices of rank $r$, and Sudakov and Tomon improved this to $D(M) = O(\sqrt{r})$. In the other direction, Göös, Pitassi and Watson gave Boolean matrices of rank $r$ with $D(M) = \tilde{\Omega}((\log r)^2)$.
Problem. Do there exist absolute constants $C, c > 0$ such that every Boolean matrix $M$ satisfies $$D(M) \le C \bigl[\log_2\bigl(2 + \operatorname{rank}_{\mathbb{R}} M\bigr)\bigr]^c ?$$
Source: Lovász and Saks (1988).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- RA
- Keywords
- AIM Open Applied Problems, Boolean matrices, communication complexity, matrix rank
References
@inproceedings{lovasz1988,
author = {Lov{\'a}sz, L{\'a}szl{\'o} and Saks, Michael},
title = {Lattices, {M}{\"o}bius functions and communication complexity},
booktitle = {Proceedings of the 29th Annual Symposium on Foundations of Computer Science ({FOCS} 1988)},
publisher = {IEEE},
year = {1988},
pages = {81--90},
doi = {10.1109/SFCS.1988.21924},
}
@article{lovett2016,
author = {Lovett, Shachar},
title = {Communication is bounded by root of rank},
journal = {J. ACM},
volume = {63},
number = {1},
year = {2016},
pages = {Art. 1, 1--9},
doi = {10.1145/2724704},
}
@article{sudakov2025,
author = {Sudakov, Benny and Tomon, Istv{\'a}n},
title = {Matrix discrepancy and the log-rank conjecture},
journal = {Math. Program.},
volume = {212},
number = {1-2},
year = {2025},
pages = {567--579},
doi = {10.1007/s10107-024-02117-9},
eprint = {2311.18524},
archivePrefix = {arXiv},
}
@article{goos2018,
author = {G{\"o}{\"o}s, Mika and Pitassi, Toniann and Watson, Thomas},
title = {Deterministic communication vs. partition number},
journal = {SIAM J. Comput.},
volume = {47},
number = {6},
year = {2018},
pages = {2435--2450},
doi = {10.1137/16M1059369},
}
@misc{aim-log-rank,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The log-rank conjecture for deterministic communication}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/290-log-rank.md},
note = {Entry 290 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00357, "The log-rank conjecture for deterministic communication", clopen.solutions.