Math Conjectures

Log-Rank Conjecture

OPENMajorConjectureProposed 1988 · Standard version

Canonical statement

There is an absolute constant CC such that every nonconstant total Boolean function f:X×Y→{0,1}f:X\times Y\to\{0,1\} satisfies
D(f)≤(1+log⁡2rank⁡RMf)C, D(f)\leq \bigl(1+\log_2\operatorname{rank}_{\mathbb R}M_f\bigr)^C,
where Mf=(f(x,y))x∈X,y∈YM_f=(f(x,y))_{x\in X,y\in Y} and D(f)D(f) is the minimum worst-case number of communicated bits in a deterministic two-party protocol computing ff.
View source LaTeX
There is an absolute constant \(C\) such that every
nonconstant total Boolean function \(f:X\times Y\to\{0,1\}\) satisfies
\[
  D(f)\leq
  \bigl(1+\log_2\operatorname{rank}_{\mathbb R}M_f\bigr)^C,
\]
where \(M_f=(f(x,y))_{x\in X,y\in Y}\) and \(D(f)\) is the minimum
worst-case number of communicated bits in a deterministic two-party
protocol computing \(f\).
TCS-015:[LovaszSaks1988LogRank][Lovett2016LogRank][Lovett2014Survey]
Theoretical computer scienceInformation theory

Notes

The log-rank conjecture, posed by Lovász and Saks in 1988 [LovaszSaks1988LogRank], asks whether the deterministic communication complexity D(f)D(f) of a total Boolean function f:X×Y→{0,1}f:X\times Y\to\{0,1\} is bounded by a fixed power of log⁡2rank⁡(Mf)\log_2\operatorname{rank}(M_f), where MfM_f is the communication matrix of ff over the reals. Since a protocol exchanging D(f)D(f) bits partitions the matrix into at most 2D(f)2^{D(f)} monochromatic rectangles, log⁡2rank⁡(Mf)\log_2\operatorname{rank}(M_f) is an elementary lower bound on D(f)D(f); the conjecture asserts that this bound is polynomially tight.

The gap between the two quantities remains wide. The best universal upper bounds on D(f)D(f) in terms of rank are far larger than any polylogarithm: Lovett showed that communication is bounded by roughly the square root of the rank [Lovett2016LogRank]. Many equivalent formulations and confirmed special cases are known, and the surrounding developments are surveyed by Lovett [Lovett2014Survey].

The conjecture is still open; resolving it requires either protocols of cost polylogarithmic in the rank for every total function, or a function whose communication complexity exceeds every fixed power of its log-rank.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.