Log-rank conjecture: D(f) ≤ polylog(rank) for Boolean matrices (best known O(√rank))
Difficulty 80: a famous 1988 conjecture whose upper bound has moved only from rank to √rank in 35 years, with an exponential gap to the best lower bound; it sits below ω (82) and quantum PCP (83) because it is a single combinatorial statement with active quantitative progress and new equivalent forms. Application value 5.5: minimal, slightly above Aaronson–Ambainis (5) through data-structure lower bounds. Leverage 48: it ties together communication complexity, rank and rectangle partitions and has a moderate conditional literature.
The problem
If a table of 0s and 1s has simple structure, can two people always compute it with a short conversation?
- 1Two people compute from split data
- 2Their task is a 0/1 table
- 3Simple table means low rank
- 4Rank gives a lower bound on bits
- 5Conjecture: that is nearly the truth
Setting. For a Boolean function , let be its communication matrix, with entry at row and column . Let be the deterministic two-party communication complexity: the fewest bits Alice and Bob must exchange in the worst case to compute .
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Communication complexity and cell-probe lower boundsTheory · host
- Then
- Log-rank conjecture: D(f) ≤ polylog(rank) for Boolean matrices (best known O(√rank))The problem
State of the art
Upper bounds. The trivial bound is . Lovett (arXiv:1306.1877; STOC 2014, J. ACM 2016) proved via discrepancy, and Sudakov and Tomon (arXiv:2311.18524, 2023; published 2025) removed the logarithm, , by showing that every rank- Boolean matrix contains a monochromatic rectangle of relative size in each dimension. This is still the best known bound as of October 2026.
Realistic applications
A proof would show that low-rank structure alone makes communication cheap, with consequences for data-structure lower bounds (via cell-probe and communication reductions), property testing, and the relation between rank and monochromatic-rectangle partitions. It is mostly of theoretical value.
What counts as solved
A proof that for all Boolean (or any bound as a partial result), or an explicit family with .
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The statement is D(f) <= polylog(rank) for Boolean matrices, or an explicit family with D(f) >= rank^Omega(1). Communication complexity is not in Mathlib, so there is no formal statement to check against. Experts review the proof or the construction. A candidate counterexample family can be partly screened by computer for small sizes, which does not settle it.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
All work is combinatorial and linear-algebraic proof; small computer searches have not suggested counterexamples.
Bottlenecks
ranked by votes- #1TheoryBeyond discrepancy-based partitioning
Both known upper bounds partition the matrix by finding large monochromatic submatrices or sparse subsets; the √rank barrier appears inherent to the discrepancy method.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Nov 30, 2023Logarithmic factor removedsource
Sudakov and Tomon proved D(f) = O(√rank) via matrix discrepancy.
- Oct 17, 2015Near-quadratic separationsource
Göös, Pitassi and Watson gave explicit functions with D(f) = Ω̃(log² rank) (FOCS 2015; SIAM J. Comput. 2018; day approximate).
- Jun 8, 2013Root-of-rank boundsource
Lovett proved D(f) = O(√r log r).