Log-rank conjecture

Unsolved problem in computer science

Prove or disprove the log rank conjecture.

More unsolved problems in computer science

In communication complexity, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix.

Let $D(f)$ denote the deterministic communication complexity of a function, and let $\operatorname {rank} (f)$ denote the rank of its input matrix $M_{f}$ (over the reals). Since every protocol using up to $c$ bits partitions $M_{f}$ into at most $2^{c}$ monochromatic rectangles, and each of these has rank at most 1,

$D(f)\geq \log _{2}\operatorname {rank} (f).$

The log-rank conjecture states that $D(f)$ is also upper-bounded by a polynomial in the log-rank: for some constant $C$,

$D(f)\leq C(\log \operatorname {rank} (f))^{C}.$

The best known upper bound, due to Lovett, states that

$D(f)\leq O{\bigl (}{\sqrt {\operatorname {rank} (f)}}\log \operatorname {rank} (f){\bigr )}.$

Recently, an approximate version of the conjecture has been disproved.